143. Reorder List

解題思路

可以把步驟拆分為三大項：

1. 把 list 分為左右半，用 slow-fast pointer 即可求得

2. 把右半 list 給 reverse，這題同樣寫過

3. 兩個 list merge，這題同樣也寫過

程式碼 

class Solution {
public:
    void reorderList(ListNode* head) {
        // find the mid point and split the list to two
        ListNode *slow = head, *fast = head;
        while(fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        
        // reverse the second part of the list
        ListNode* prev = nullptr, *second = slow->next;
        ListNode* next;
        slow->next = nullptr;
        while(second != nullptr)
        {
            next = second->next;
            second->next = prev;
            prev = second;
            second = next;
        }
        
        // merge two list
        ListNode *firstHead = head, *secondHead = prev, *next1, *next2;
        while(secondHead != nullptr)
        {
            next1 = firstHead->next;
            next2 = secondHead->next;
            firstHead->next = secondHead;
            secondHead->next = next1;
            firstHead = next1;
            secondHead = next2;
        }
    }
};