LeetCode 143. Reorder List [Medium] [C++] 解題筆記

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,

reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

想法:

    這題應該算是單純的實作題，先用 Two pointers 找到 linked list 的中間點 m，然後將 list 從 m 切成兩段，

l1 與 l2，將 l2 reverse 之後再與 l1 合併，合併方式為從 l1 的開頭開始遍歷每間隔一個 node insert 一個 l2 的 node，

直到遍歷到 l1 或 l2 的結尾。

完整程式碼:

class Solution {

public:

void reorderList(ListNode* head) {

if (head == nullptr || head->next == nullptr) { return; }

ListNode* first = head;

ListNode* second = head;

while (first != nullptr && first->next != nullptr) {

first = first->next->next;

second = second->next;

}

//cout<<second->val<<endl;

ListNode* pre = nullptr;

ListNode* cur = second->next;

second->next = nullptr;

while (cur != nullptr) {

auto tmp = cur->next;

cur->next = pre;

pre = cur;

cur = tmp;

}

first = head;

second = pre;

while (first != nullptr && second != nullptr) {

auto next = first->next;

first->next = second;

second = second->next;

first->next->next = next;

first = next;

}

return;

}

};