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 Plain-English Breakdown

You are given a linked list. You need to fold it in half, taking one node from the front, then one from the back, then the second from the front, the second from the back, and so on. You must restructure the actual next pointers of the nodes, not just overwrite the .val properties.

Constraints to note:

• The list length is up to 5 \times 10^4.
• You cannot just store values and create new nodes; you must manipulate the existing pointers.

Brute Force Analysis

A brute force method without extra space would be to pick the first node, then traverse the entire list to find the very last node, and link them. Then take the second node, traverse the whole list again to find the second-to-last node, and link them.

• Time Cost: Finding the last node takes N steps. Finding the second-to-last takes N-1 steps, then N-2, etc. This is N + (N-1) + (N-2) \dots = O(N^2) time.
• Why it fails: For 50,000 nodes, O(N^2) is 2.5 billion operations. It will absolutely Time Out. We need an O(N) approach.

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. ✓

Code Walkthrough

1. Base Case: If the list is empty or has only one node (not head or not head.next), it's already reordered, so return.
2. Find the Middle (Step 1): We initialize slow and fast pointers at the head. The while fast and fast.next condition ensures slow lands on the first middle node (node 2 in a 4-node list).
3. Sever the Halves (Step 2a): second = slow.next gives us the head of the second half. We MUST set slow.next = None to permanently sever the first half from the second half. If we don't, we will create an infinite loop/cycle during the weave.
4. Reverse Second Half (Step 2b): We iterate through the second half, reversing pointers exactly as we do in a standard "Reverse Linked List" problem. At the end, prev points to the new head of our reversed second half. We reassign second = prev.
5. The Weave (Step 3): We set first = head. We loop while second: because the second half is guaranteed to be equal in length or strictly shorter than the first half.
6. Rewiring: We temporarily save the next nodes (f_next, s_next) so we don't lose them. We point first.next to second. We point second.next to f_next. Then we advance both first and second to the saved next nodes.

Complexity

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

Derivation:

• Time Complexity: Finding the middle takes N/2 iterations. Reversing the second half takes N/2 iterations. Weaving takes N/2 iterations. Total time is roughly 1.5N, which simplifies to O(N) time.
• Space Complexity: We only create a few pointer variables (slow, fast, first, second, prev, nxt), regardless of how massive the linked list is. No arrays or recursion are used, so auxiliary space is strictly O(1).

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.