143 - Reorder List

Problem

Given the head of a singly linked list, the list is

L0 -> L1 -> ... -> Ln-1 -> Ln

Reorder it to

L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...

Nodes may not be swapped by value — only the links may change.

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

• The number of nodes is in the range [1, 5 * 10^4]
• 1 <= Node.val <= 1000

Approach

The target order alternates front, back, front, back. The front is easy to walk; the back is not, because a singly linked list only reads forwards.

1. find the middle
2. cut, and reverse everything after the cut
3. walk l from the head and r from the reversed half, relinking as you go

1 -> 2 -> 3 -> 4 -> 5            slow stops on 3

1 -> 2 -> 3 | nullptr            cut: slow->next = nullptr
            5 -> 4               reverse what was after the cut, prev = 5

l=1 r=5    1 -> 5 -> 2 ...
l=2 r=4    2 -> 4 -> 3 ...
r = null, stop                   1 -> 5 -> 2 -> 4 -> 3

class Solution {
public:
    void reorderList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return;
        ListNode* slow = head, *fast = head;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* curr = slow->next;
        slow->next = nullptr;
        ListNode* prev = nullptr;
        while(curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }

        ListNode* l = head, *r = prev;
        while(r) {
            ListNode* t1 = l->next, *t2 = r->next;
            l->next = r;
            r->next = t1;
            l = t1;
            r = t2;
        }
    }
};

• time: O(n) - one pass to the middle, one to reverse, one to zip
• space: O(1) - a fixed handful of pointers