Reorder List

Reorder List looks fiddly but is really three small linked-list techniques stitched together: find the middle, reverse a list, and merge two lists. Master those three and this problem — and many others — fall out for free.

The slow way first

The easy idea: copy every node into an array, then walk it from both ends — front, back, front, back — re-linking as you go. That works and is O(n) time, but it uses O(n) extra space for the array. In an interview the follow-up is always "can you do it with O(1) space?" The answer is yes, by manipulating pointers directly.

The idea: middle, reverse, weave

Split the work into three phases that each touch only pointers:

1. Find the middle with a slow/fast pointer pair. When fast runs off the end, slow is at the midpoint. Cut the list there into a front half and a back half.
2. Reverse the back half in place, so its last node becomes its first.
3. Weave the two halves: take one node from the front, then one from the reversed back, alternating until both are spent.

For 1 -> 2 -> 3 -> 4: the middle splits it into 1 -> 2 and 3 -> 4. Reversing the back half gives 4 -> 3. Weaving the front (1, 2) with the reversed back (4, 3) produces 1 -> 4 -> 2 -> 3.

Walk through it

Step through the animation. In phase 1 the slow and fast markers move and slow lands on node 2. The list is cut, and the back half drops to a lower row, gets reversed into 4 -> 3, and is then woven back into the top: 1 -> 4, then 4 -> 2, then 2 -> 3.

Pseudocode

find middle with slow/fast; cut list into first half and second half
reverse the second half in place        # 3 -> 4 becomes 4 -> 3
walk both halves together:
    splice one node from the front half
    splice one node from the reversed back half
    repeat until the back half is exhausted

The Python solution

def reorder_list(head):
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    second = slow.next
    slow.next = None
    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt
    first = head
    while prev.next:
        first.next, first = prev, first.next
        prev.next, prev = first, prev.next

• Lines 3-5 are the fast/slow walk: fast moves two steps for each one of slow, so slow ends at the middle.
• second = slow.next then slow.next = None cuts the list into two independent halves.
• Lines 9-13 are the classic in-place reversal of the back half using prev/second/nxt.
• Lines 15-17 are the weave: each turn splices a back-half node after a front-half node, then advances both pointers. The loop ends when prev.next runs out.

Complexity

Each phase is a single linear pass, so the whole thing is O(n) time. Because we only re-point existing nodes, the in-place version uses O(1) extra space.

When this pattern shows up

Practice