143. Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-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.

// Iteration with 3 passes
void reorderList(ListNode* head) { // time: O(n); space: O(1)
    if (!head || !head->next || !head->next->next) return;
    // Use fast & slow pointers to find the middle node of the list
    ListNode *fast = head, *slow = head;
    while (fast->next && fast->next->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    ListNode* mid = slow->next;
    slow->next = nullptr;
    // Reverse the second half list
    ListNode *cur = mid, *pre = nullptr, *nex = nullptr;
    while (cur) {
        nex = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nex;
    }
    // Reorder processing
    // pre is the head of the second half list
    ListNode *p1 = head, *p2 = pre;
    while (p1 && p2) {
        nex = p1->next;
        p1->next = p2;
        p2 = p2->next;
        p1->next->next = nex;
        p1 = nex;
    }
}

// Stack
void reorderList(ListNode* head) { // time: O(n); space: O(n)
    if (!head || !head->next || !head->next->next) return;
    stack<ListNode*> st;
    ListNode* cur = head;
    while (cur) {
        st.push(cur);
        cur = cur->next;
    }
    int cnt = (st.size() - 1) / 2;
    cur = head;
    while (--cnt >= 0) {
        ListNode* t = st.top(); st.pop();
        ListNode* nex = cur->next;
        cur->next = t;
        t->next = nex;
        cur = nex;
    }
    st.top()->next = nullptr; // remember to cut the list to avoid cyclic list
}