4.9.3 — Reorder List

LeetCode 143 · Medium · ★ Blind 75

The problem

Given L0 → L1 → … → Ln, rearrange it into L0 → Ln → L1 → Ln−1 → … — first node, last node, second node, second-to-last, and so on. You must move the nodes, not just their values.

1 → 2 → 3 → 4        becomes   1 → 4 → 2 → 3
1 → 2 → 3 → 4 → 5    becomes   1 → 5 → 2 → 4 → 3

The pattern

The obvious problem is that a singly linked list cannot be walked backwards, and the target order needs the last node second.

Three techniques, applied in order, solve it:

1. Find the middle with slow and fast pointers.
2. Reverse the second half. Now the back of the list is walkable from the front.
3. Weave the two halves together, taking one node from each in turn.

Each step is a problem you have already met. That is what makes this a good problem — it tests whether the pieces are automatic.

1 → 2 → 3 → 4 → 5 → 6

split:     1 → 2 → 3        4 → 5 → 6
reverse:   1 → 2 → 3        6 → 5 → 4
weave:     1 → 6 → 2 → 5 → 3 → 4

Step 1 — finding the middle

Move slow one node at a time and fast two at a time. When fast reaches the end, slow is halfway.

slow, fast = head, head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

Which node slow lands on depends on the loop condition, and it matters here.

• while fast and fast.next gives the second middle on an even-length list. For 1→2→3→4, slow ends at 3.
• while fast.next and fast.next.next gives the first middle. For 1→2→3→4, slow ends at 2.

This problem wants the first version, so that the second half is the same size or one shorter. Then the weave always ends cleanly.

Rather than memorise which is which, trace it on a four-node list before committing. Five seconds, and it removes the most common source of off-by-one bugs in linked-list problems.

The solution

Python

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head or not head.next:
            return

        # 1. find the middle
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 2. reverse the second half, and cut it off from the first
        second = slow.next
        slow.next = None
        prev = None
        while second:
            nxt = second.next
            second.next = prev
            prev = second
            second = nxt
        second = prev                # head of the reversed second half

        # 3. weave
        first = head
        while second:
            f_next, s_next = first.next, second.next
            first.next = second
            second.next = f_next
            first, second = f_next, s_next

TypeScript

function reorderList(head: ListNode | null): void {
  if (!head || !head.next) return;

  let slow = head, fast: ListNode | null = head;
  while (fast && fast.next) {
    slow = slow.next!;
    fast = fast.next.next;
  }

  let second = slow.next;
  slow.next = null;
  let prev: ListNode | null = null;
  while (second) {
    const nxt = second.next;
    second.next = prev;
    prev = second;
    second = nxt;
  }
  second = prev;

  let first: ListNode | null = head;
  while (second) {
    const fNext = first!.next, sNext = second.next;
    first!.next = second;
    second.next = fNext;
    first = fNext;
    second = sNext;
  }
}

slow.next = None is the line people forget. Without it the first half still points into the second half, which has just been reversed, and you get a cycle. The list must be cut in two before the halves are woven.

The weave loops on second, not on first. The first half is the same length or one longer, so the second half runs out first. Looping on first would dereference a null on the last step.

Save both next pointers before rewiring. The moment first.next = second executes, the old first.next is gone. Same discipline as 4.9.1.

Trace on 1 → 2 → 3 → 4

After step 1, slow is at 3. Second half is 3 → 4, cut off, leaving 1 → 2.

After step 2, second half is 4 → 3.

Weave: first = 1, second = 4. Save f_next = 2, s_next = 3. Then 1 → 4, 4 → 2. Move on: first = 2, second = 3. Save f_next = null, s_next = null. Then 2 → 3, 3 → null.

Result 1 → 4 → 2 → 3. ✓

Complexity

O(n) time — three passes, each linear. O(1) space, since everything is pointer rewiring.

The easy alternative

Put every node into an array, then walk it from both ends and rewire:

nodes = []
node = head
while node:
    nodes.append(node)
    node = node.next

i, j = 0, len(nodes) - 1
while i < j:
    nodes[i].next = nodes[j]
    i += 1
    if i == j: break
    nodes[j].next = nodes[i]
    j -= 1
nodes[i].next = None

O(n) time and O(n) space. It is much easier to get right, and it is a perfectly acceptable answer if you say the space cost out loud and offer the O(1) version as the improvement.

Where this goes next

The three pieces are the whole toolkit for this chapter:

• Palindrome Linked List — find the middle, reverse the second half, compare. Two of the three steps.
• Sort List — find the middle, sort each half, merge. Merge sort on a list.
• Split Linked List in Parts — the middle-finding idea generalised to k pieces.

The rule: a singly linked list cannot be walked backwards, so when a problem needs the back, reverse a portion of it.

What the interviewer will push on

"Why do you cut the list at the middle?" Otherwise the first half still points into the reversed second half and you create a cycle.

"Which middle does your slow-fast loop find?" Know it and be able to say why, by tracing a four-node list.

"Why does the weave loop on the second half?" The second half is never longer, so it finishes first.

"Can you do it without O(n) space?" Yes, this version. The array version is the easier one to write and worth offering first.

One thing to volunteer: name the three steps before writing any code. "Find the middle, reverse the second half, weave." Then write them one at a time. This problem punishes people who start typing before they have the plan.

Next: 4.9.4 Remove Nth Node From End of List — slow and fast pointers again, but now with a fixed gap between them.