leetcode-textbook

0143 - Reorder List

Difficulty: Medium Pattern: Linked List LeetCode: https://leetcode.com/problems/reorder-list/

Concepts used

Problem

You are given the head of a singly linked list L0 -> L1 -> ... -> Ln-1 -> Ln. Reorder it in place to L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> .... You may not modify the values in the nodes – only the links between nodes may change. Return nothing (mutate the list in place).

Signature:

void reorderList(ListNode head)

Examples:

Input:  head = [1,2,3,4]      Output: [1,4,2,3]
Input:  head = [1,2,3,4,5]    Output: [1,5,2,4,3]
Input:  head = [1]            Output: [1]

Intuition

The target order interleaves the front half of the list with the back half reversed: L0, L1, L2, ... becomes L0, Ln, L1, Ln-1, L2, .... Think of shuffling a deck by taking one card from the top, one from the bottom, one from the top, one from the bottom – except the “bottom” cards must be read in reverse order. A linked list only points forward (each node’s pointer is an arrow to the next node), so we cannot read the bottom half backwards directly. But we can flip its arrows, and once flipped, walking that half forward visits the bottom cards in exactly the reverse order we need.

Smallest meaningful case, 1 -> 2 -> 3 -> 4 (target 1 -> 4 -> 2 -> 3):

So the solution is three steps, each a technique practiced on its own:

  1. Find the middle, using the trick from Middle of the Linked List (LC 876): one pointer takes one step per turn, another takes two; when the fast one runs off the end, the slow one is sitting on the middle.
  2. Reverse the second half, using the arrow-flipping dance from Reverse Linked List (LC 206): for each node, save its next arrow, point the node backward at the previous one, advance.
  3. Interleave the two halves: hold one finger on each and stitch them together two nodes at a time.

After step 2, a finger walking the reversed back half meets Ln, Ln-1, Ln-2, ... – exactly the order those nodes must appear between the front-half nodes – so the interleave is just “attach one from each side, repeat”. Before interleaving we split the list cleanly with slow.next = null; otherwise the front half stays chained into the reversed back half and we would walk in a circle. Everything is in-place pointer surgery: no arrays, no recursion, no new nodes.

Checkpoint A – The interleave recipe

Pause and pick before expanding. A wrong first guess teaches more than a fast right one.

Q1 (recall). List the three steps of reorderList in order.

Show answer **(b)** -- first locate the split, then flip the back half so it reads `Ln, Ln-1, ...`, then stitch one-from-each-side together.

Q2 (comprehend). Right after reversing the back half, the code sets slow.next = null. Why?

Show answer **(b)** -- without it the front half's tail still points into the reversed back half, and the interleave would chase its own tail forever.

Pseudocode

function reorderList(head):
    if head is null or head.next is null:
        return                       # nothing to reorder

    # 1. find the middle (slow stops on first-middle for even length)
    slow <- head
    fast <- head
    while fast.next is not null and fast.next.next is not null:
        slow <- slow.next
        fast <- fast.next.next

    # 2. split and reverse the back half
    second <- reverse(slow.next)
    slow.next <- null                # detach front half from the (now reversed) back half

    # 3. interleave: front = head, back = second
    first <- head
    while second is not null:
        tmpFirst <- first.next
        tmpSecond <- second.next
        first.next <- second         # front node -> back node
        second.next <- tmpFirst      # back node -> next front node
        first  <- tmpFirst
        second <- tmpSecond

function reverse(head):
    prev <- null
    curr <- head
    while curr is not null:
        next <- curr.next
        curr.next <- prev
        prev <- curr
        curr <- next
    return prev

Java Solution

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

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

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

        ListNode second = reverse(slow.next);
        slow.next = null;                 // detach front half from back half

        ListNode first = head;
        while (second != null) {
            ListNode tmpFirst = first.next;
            ListNode tmpSecond = second.next;
            first.next = second;
            second.next = tmpFirst;
            first = tmpFirst;
            second = tmpSecond;
        }
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

The slow/fast loop is the same first-middle variant used in Palindrome: on an even-length list slow stops on the left-middle, so the back half has exactly as many nodes as the front. slow.next = null is the line that actually splits the list into two – without it the front half’s tail still points into the reversed back half and the interleave would form a cycle. In the interleave loop we save both first.next and second.next before rewriting, because both links are about to be overwritten; then we splice (first -> second -> old first.next) and step both fingers forward. The loop is driven by second (the back half), which is never longer than the front half, so first never falls off the end – on odd total length the leftover front-half node stays correctly as the final tail.

Complexity

Time:  O(n)  -- three linear passes (middle, reverse, interleave), each touching ~n/2 nodes
Space: O(1)  -- a constant number of pointers; nodes are rewired in place

Dry-Run

Input head = [1, 2, 3, 4, 5]. Nodes A=1, B=2, C=3, D=4, E=5.

Step 1 – find middle:

iteration slow after fast after
start A A
1 B C
2 C E

fast.next is null (E.next), loop stops. slow on C.

Step 2 – reverse back half slow.next = D->E: result second = E->D. Then slow.next = null: front half = A->B->C->null.

Step 3 – interleave (first walks A,B,C; second walks E,D):

iter first second tmpFirst tmpSecond after splice
1 A E B D A->E->B
2 B D C null B->D->C

second is now null -> stop. first = C, but the loop has ended; C stays as the tail with C.next already null from the detach step.

Final chain read from head: A -> E -> B -> D -> C = [1, 5, 2, 4, 3]. Correct.

Even-length [1, 2, 3, 4]: slow stops on B; back half C->D reverses to D->C; interleave gives A->D->B->C = [1, 4, 2, 3]. Correct.

Checkpoint B – Trace and stress it

Q1 (apply). Trace reorderList on head = [1, 2, 3, 4, 5, 6]. What is the final list?

Show answer **(a)** -- slow stops on 3, the back half `4->5->6` reverses to `6->5->4`, and interleaving front `[1,2,3]` with it yields `1, 6, 2, 5, 3, 4`.

Q2 (analyze). What goes wrong if you omit slow.next = null after reversing the back half?

Show answer **(a)** -- the unbroken link turns the two halves into a loop, so the splice pointers never reach `null` and the list is corrupted.

Q3 (transfer). The interleave loop saves both first.next and second.next before splicing. Why must both be saved, and what breaks if only one is?

Show answer The splice overwrites *both* links -- `first.next` becomes the back node and `second.next` becomes the next front node -- so if either successor is not saved first that finger loses its way forward and points at the wrong node, tangling the rest of the weave.

Common mistakes