143. Reorder List

Reorder List looks fiddly until you notice it’s three problems you already know, stapled together: find the middle, reverse a list, and merge two lists. None of the three is hard on its own, and chaining them is exactly the kind of composition the linked-list patterns reward. Do it with pointers only and you never spend more than $O(1)$ extra space.

The problem

Given the head of a singly linked list L0 → L1 → … → Ln, rewrite the links so it reads L0 → Ln → L1 → Ln-1 → L2 → … — first node, last node, second node, second-to-last, and so on. You have to relink actual nodes; swapping values is off the table. (Full statement on LeetCode.)

So 1 → 2 → 3 → 4 → 5 becomes 1 → 5 → 2 → 4 → 3.

Intuition: fold the list in half

Stare at the target order and read it as two zippers meshing. The front of the list stays put — L0, L1, L2, … — while the back of the list arrives in reverse — Ln, Ln-1, Ln-2, …. Interleave those two sequences and you have the answer.

That reframing hands you the whole plan:

1. Split the list into a front half and a back half. A slow/fast pointer walks the split: when fast reaches the end, slow sits at the midpoint.
2. Reverse the back half in place, so its last node becomes its head — now it hands you Ln, Ln-1, … one node at a time.
3. Merge the two halves by alternating: take one from the front, one from the reversed back, repeat.

Because the back half has the same length as the front (or one fewer, for odd n), the merge runs out cleanly at the tail. Every step is a linear scan, and nothing but a few pointers ever gets allocated.

Solution

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;

        // Step 1: slow lands on the last node of the first half.
        // Stopping on fast.next / fast.next.next keeps slow before the midpoint
        // so the front half is never shorter than the back.
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Step 2: reverse everything after slow, then sever the two halves.
        ListNode second = slow.next;
        slow.next = null;               // front half now ends cleanly
        ListNode prev = null;
        while (second != null) {
            ListNode next = second.next;
            second.next = prev;         // flip the link backward
            prev = second;
            second = next;
        }
        second = prev;                  // prev is the new head of the reversed half

        // Step 3: weave the two halves together, front then back.
        ListNode first = head;
        while (second != null) {
            ListNode f = first.next, s = second.next;
            first.next = second;        // L_i -> L_{n-i}
            second.next = f;            // L_{n-i} -> L_{i+1}
            first = f;
            second = s;
        }
    }
}

The one subtlety is where slow stops. Guarding the loop on fast.next and fast.next.next means that for an even-length list slow ends on the last node of the front half, so the front half is the same size or one longer than the back. That keeps first from running past the end during the merge.

Complexity

	Time	Space
Split + reverse + merge	$O(n)$	$O(1)$

Three sequential passes over the list — finding the middle, reversing, merging — add up to $O(n)$, and every pass reuses the same handful of pointer variables.

In an interview

Don’t try to invent this in one shot. Say the decomposition out loud first — “I’ll find the middle with slow/fast, reverse the second half, then merge the two halves” — because naming the three sub-problems is what shows you recognized the pattern rather than groping for it. Then implement each piece; interviewers are usually happy to see you lean on Reverse Linked List as a known building block.

The classic trap is the split point. If your slow/fast loop leaves slow one node too far, the reversed back half is longer than the front and the merge either drops a node or walks off the end — worth tracing a 4-node and a 5-node case on the whiteboard to prove both parities work. The fast/slow midpoint trick itself is the same tool behind Linked List Cycle, and the merge step is a stripped-down Merge Two Sorted Lists. The linked-list patterns hub collects the rest of the family.

References

• LeetCode 143 — Reorder List