LeetCode 143 重排链表
🟠 中等偏上 https://leetcode.cn/problems/reorder-list/description/
思路：找到中间节点，反转后面的节点，再两条链表拼接。
- 找到中间节点：偶数为前一个
- `if(fast->next->next){
fast = fast->next->next;
slow = slow->next;`
反转链表
ListNode* fake_head = new ListNode();
ListNode* cur = slow->next;
slow->next = nullptr;
while(cur!=nullptr){
ListNode* tmp = cur->next;
cur->next = fake_head->next;
fake_head->next = cur;
cur = tmp;
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast->next!=nullptr){
if(fast->next->next){
fast = fast->next->next;
slow = slow->next;
}else{
fast = fast->next;
}
}
//反转链表
ListNode* fake_head = new ListNode();
ListNode* cur = slow->next;
slow->next = nullptr;
while(cur!=nullptr){
ListNode* tmp = cur->next;
cur->next = fake_head->next;
fake_head->next = cur;
cur = tmp;
}
// ListNode* i = head;
// while(i){
// cout<<i->val<<endl;
// i = i->next;
// }
ListNode* cur_ret = head;
ListNode* reverse_cur = fake_head->next;
while(reverse_cur!=nullptr){
ListNode* tmp = reverse_cur->next;
reverse_cur->next = cur_ret->next;
cur_ret->next = reverse_cur;
reverse_cur = tmp;
cur_ret = cur_ret->next->next;
}
// cout<<slow->val<<endl;
}
};