Reorder List

Before we start

This problem sits at the intersection of three techniques you have already learned. It is the clearest example of how linked list patterns compose: finding the middle (Chapter 4.2) + reversing a list (Chapter 4.3) + merging two lists (Chapter 4.4) = a problem that looks hard but writes itself once you see the structure. By the end you will be able to:

• Break the problem into three named sub-problems and solve each independently.
• Write the full solution from memory, correctly handling the odd/even length edge.
• Trace the full 5-node example step by step.

Picture this first (no code yet)

The actual problem

Reorder List (LC #143):

Given a linked list 1 → 2 → 3 → 4 → 5, reorder it in-place to 1 → 5 → 2 → 4 → 3.

The pattern: node 1, then node n, then node 2, then node n−1, and so on.

No extra array allowed — this must be done by pointer rewiring in O(n) time, O(1) space.

First, the slow way (so you feel the pain)

Copy all node references into an array. Use two-pointer technique on the array (left, right) to build the new order. O(n) time but O(n) space for the array. For a list of 10 million nodes, that is 80 MB of extra memory just for pointers. The in-place approach uses O(1) space — three pointer variables during each step.

The turning point

The one idea to remember

The three steps in code

def reorderList(head) -> None:
    if not head or not head.next:
        return

    # ── Step 1: Find the middle (first middle for even length) ──────
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # slow is now the last node of the first half

    # ── Step 2: Reverse the second half ─────────────────────────────
    second = slow.next   # head of second half
    slow.next = None     # cut the list: disconnect first and second halves

    prev, curr = None, second
    while curr:
        nxt       = curr.next
        curr.next = prev
        prev      = curr
        curr      = nxt
    second = prev        # prev is now the head of the reversed second half

    # ── Step 3: Merge the two halves alternately ────────────────────
    first = head
    while second:                  # second half is always ≤ first half in length
        tmp1        = first.next   # save next of first
        tmp2        = second.next  # save next of second
        first.next  = second       # wire: first → second
        second.next = tmp1         # wire: second → (next of first)
        first       = tmp1         # advance first
        second      = tmp2         # advance second

Note: this function modifies the list in-place and returns None (the list is modified through head).

Watch it happen, frame by frame

Input: 1 → 2 → 3 → 4 → 5

Step 1: Find middle

slow=1, fast=2
Iter 1: slow=2, fast=4
Iter 2: slow=3, fast=None (fast=4.next.next=None — wait, fast=4, fast.next=5, fast.next.next=None)

Let me re-trace with fast=head.next:
slow=1, fast=2
Iter 1: slow=2, fast=4   (fast=2.next.next=4)
Iter 2: slow=3, fast=None  (fast=4.next.next=None)

slow = node3 (last of first half). ✅

Step 2: Reverse second half

second = node4.  slow.next = None → first half: 1→2→3→None

Reverse 4→5→None:
prev=None, curr=4
  nxt=5, 4.next=None, prev=4, curr=5
  nxt=None, 5.next=4, prev=5, curr=None

second = node5.  Reversed: 5→4→None

Step 3: Merge alternately

first=node1, second=node5

Iter 1:
  tmp1=node2, tmp2=node4
  1.next=5, 5.next=2
  first=node2, second=node4
  List so far: 1→5→2→...

Iter 2:
  tmp1=node3, tmp2=None
  2.next=4, 4.next=3
  first=node3, second=None
  List so far: 1→5→2→4→3→None

second=None → while exits.

Final: 1→5→2→4→3  ✅

The even-length case: 1 → 2 → 3 → 4

Step 1: slow=1, fast=2

Iter 1: slow=2, fast=4  (fast=2.next.next=4)
Iter 2: fast.next=None → exit.
slow = node2. (first middle of even list)

First half: 1→2→None.  Second half: 3→4→None.

Step 2: Reverse 3→4 → 4→3→None. second=node4.

Step 3:

first=1, second=4
Iter 1: tmp1=2, tmp2=3. 1.next=4, 4.next=2. first=2, second=3.
Iter 2: tmp1=None, tmp2=None. 2.next=3, 3.next=None. first=None, second=None.

Final: 1→4→2→3  ✅

Why slow.next = None (cutting the list) matters

Without the cut, when you reverse the second half, the first node of the second half (originally pointing forward) still has its old next pointer — which points to nodes in the first half. That creates a cycle during the merge step, leading to an infinite loop. The cut (slow.next = None) cleanly separates the two halves so the reversal and merge operate on independent lists.

Where to spot this pattern

Trigger words:

• "reorder list" / "rearrange list" in place
• "interleave front and back"
• "palindrome linked list" — almost the same: find middle, reverse second, compare (no merge step)
• any problem that needs the "second half reversed" of a list

5 disguises:

1. Reorder List (LC #143): find middle → reverse → merge alternately.
2. Palindrome Linked List (LC #234): find middle → reverse second → compare (no merge).
3. Sort List (LC #148): find middle → recursive sort each half → merge (Chapter 4.4).
4. Reverse Nodes in Even Length Groups: find group boundaries, reverse even groups — partial reversal (Chapter 4.3).
5. Odd Even Linked List (LC #328): separate odd-indexed and even-indexed nodes into two chains, then append even chain to odd — same split-and-rejoin idea.

Common traps

# Step 1: Find middle (first middle)
slow, fast = head, head.next
while fast and fast.next:
    slow = slow.next; fast = fast.next.next

# Step 2: Reverse second half
second = slow.next;  slow.next = None   # ← cut!
prev = None
while second:
    nxt = second.next; second.next = prev; prev = second; second = nxt
second = prev

# Step 3: Merge alternately
first = head
while second:
    tmp1, tmp2 = first.next, second.next
    first.next = second;  second.next = tmp1
    first, second = tmp1, tmp2

Check yourself

Practice problems

Next up: Flatten a Linked List — when nodes have both a next pointer and a child pointer pointing to another list, a stack or iterative DFS-style unrolling merges all sub-lists into one.