# 143 - Reorder List

解法一 - Fast & Slow Pointer

跟上一題一樣，我們可以先找到 list 中點，把後半 list reverse，然後就依序連接前半跟後半的 node。這樣做的好處是效率很高，時間複雜度 O(N)，空間複雜度 O(1)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head or !head->next)
            return;

        // Find the middle of list
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // reverse the second half of the list
        ListNode* second = reverse(slow);
        ListNode* first = head;

        // construct the new list by interleaving two halves
        while(first != NULL && second != NULL) {
            ListNode* tmp = first->next;
            first->next = second;
            first = tmp;

            tmp = second->next;
            second->next = first;
            second = tmp;
        }

        if(first != NULL)
            first->next = NULL;
    }

private:
    ListNode* reverse(ListNode* head) {
        ListNode* prev = NULL;

        while(head != NULL) {
            ListNode* next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }

        return prev;
    }
};

Runtime: 44 ms, faster than 95.04% of C++ online submissions for Reorder List. Memory Usage: 12.1 MB, less than 88.24% of C++ online submissions for Reorder List.

解法二 - vector 儲存 + Two Pointer

這個解法先使用 vector 來存所有的 node，然後就用兩個 pointer 來建立 interleaving 的 list。實作如下：

class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head || !head->next) return;

        vector<ListNode*> vl;
        while (head) { 
            vl.push_back(head); 
            head = head->next;
        }

        // reassign the next pointer
        int i = 0, j =  vl.size() - 1;
        while ( i + 1 < j ) {
            vl[i]->next = vl[j];
            vl[j]->next = vl[i+1];
            ++i, --j;
        }

        vl[j]->next = NULL;
    }
};