Reorder List: three operations you already know

[1, 2, 3, 4, 5] becomes [1, 5, 2, 4, 3]. The front and back are zipped together. When I first looked at this problem I started sketching a custom approach — some clever in-place dance that would visit nodes in the right order. Three minutes in I stopped. The shape of the output was familiar: front alternating with back. I had seen that pattern before, just not in a linked list context.

The real structure of the problem is: take the first half as-is, take the second half reversed, then interleave them. Once I saw that, the algorithm wrote itself. Three operations, each already solved.

What the constraints are telling you

The list has up to 50,000 nodes. Node values run from 1 to 1000 — irrelevant here, because you are not sorting or comparing values, only rearranging pointers. The constraint that actually matters is "you may not modify values in nodes, only nodes themselves." That rules out the value-swap trick and forces you to rewire the links.

50,000 nodes means O(n²) is borderline dangerous. An approach that repeatedly walks to the tail and splices it in would be roughly 2.5 billion pointer operations. The practical ceiling here is O(n).

The other thing the constraint reveals: you need simultaneous access to both ends of the list. Arrays give you that for free via index arithmetic. A linked list does not — you cannot jump to index n - 1 without walking there first. That tension is the entire problem. Either you accept the O(n) auxiliary space to get that random access, or you find a way to restructure the list so both ends meet you.

Brute force: collect into an array, rewire with two pointers

The most direct path: dump all nodes into an array, then use two pointers to rewire them. Left starts at 0, right at n - 1. Each iteration: connect left to right, advance left; connect right to the new left, retreat right. Stop when they meet.

class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head or not head.next:
            return
 
        nodes = []
        cur = head
        while cur:
            nodes.append(cur)
            cur = cur.next
 
        left, right = 0, len(nodes) - 1
        while left < right:
            nodes[left].next = nodes[right]
            left += 1
            if left == right:
                break
            nodes[right].next = nodes[left]
            right -= 1
 
        nodes[left].next = None

public class Solution {
    public void ReorderList(ListNode head) {
        if (head == null || head.next == null) return;
 
        var nodes = new List<ListNode>();
        var cur = head;
        while (cur != null) {
            nodes.Add(cur);
            cur = cur.next;
        }
 
        int left = 0, right = nodes.Count - 1;
        while (left < right) {
            nodes[left].next = nodes[right];
            left++;
            if (left == right) break;
            nodes[right].next = nodes[left];
            right--;
        }
 
        nodes[left].next = null;
    }
}

Let me step through [1, 2, 3, 4] with this. After collection, nodes = [1, 2, 3, 4], left = 0, right = 3.

Iteration 1: nodes[0].next = nodes[3] — node 1 points to node 4. Advance left to 1. left != right, so continue. nodes[3].next = nodes[1] — node 4 points to node 2. Retreat right to 2.

Iteration 2: nodes[1].next = nodes[2] — node 2 points to node 3. Advance left to 2. Now left == right, so break.

After the loop: nodes[2].next = None — node 3 points to null.

The chain: 1 -> 4 -> 2 -> 3 -> null. Correct.

The if left == right: break inside the loop handles the odd-length case. After nodes[left].next = nodes[right] you advance left before checking, so on a 5-node list when pointers converge on the same node, that node gets assigned next = None and you exit cleanly rather than making it point at itself.

O(n) time, O(n) space. The O(n) space is fine for n = 50,000 — we are talking a few hundred KB of pointers. But there is an O(1) space version, and it is worth knowing because it chains exactly the primitives this linked-list series has been building.

The O(1) approach: decompose into three familiar problems

The decomposition:

1. Find the midpoint of the list (slow/fast pointers).
2. Reverse the second half — this is LeetCode 206 verbatim.
3. Merge alternating from the first half and the reversed second half.

The state of [1, 2, 3, 4, 5] at each stage:

Each sub-problem is independent. None of them need the others to work. That composability is the point — and it is why the code below reads almost like assembling three previously solved functions.

Step 1: slow/fast pointers to find the midpoint

If you have done Middle of the Linked List (876), this is identical. slow moves one step; fast moves two. When fast runs out of room, slow is at the midpoint.

The termination condition is while fast.next and fast.next.next. This stops slow at the last node of the first half, not the first node of the second half. For [1, 2, 3, 4]: slow lands on 2, and slow.next (which is 3) becomes the head of the second half. For [1, 2, 3, 4, 5]: slow lands on 3, and slow.next (node 4) begins the second half.

slow, fast = head, head
while fast.next and fast.next.next:
    slow = slow.next
    fast = fast.next.next
 
second = slow.next
slow.next = None  # sever the first half

Do not skip the sever. Without slow.next = None, the first half still points into the second half. The merge step would then create a cycle.

The wrong condition is while fast and fast.next. That stops slow one step further: on a 5-node list, slow lands on node 3 instead of node 2, and the second half starts from node 4, losing node 3.

Let me trace the pointer positions for [1, 2, 3, 4, 5] step by step:

Step 2: reverse the second half

The exact code from Reverse Linked List (206):

prev = None
cur = second
while cur:
    nxt = cur.next
    cur.next = prev
    prev = cur
    cur = nxt
second = prev

prev starts at None because the new tail must point to null. After the loop, prev holds the new head of the reversed segment.

For [4, 5], the trace:

State before: prev=None, cur=4, 4->5->null

Iteration 1: nxt=5, 4.next=None, prev=4, cur=5. Now 4->null.

Iteration 2: nxt=None, 5.next=4, prev=5, cur=None. Now 5->4->null.

Loop ends. second = prev = 5. The reversed second half is 5 -> 4 -> null.

ListNode prev = null, cur = second;
while (cur != null) {
    ListNode nxt = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
}
second = prev;

Step 3: merge alternating

Both halves are null-terminated. The merge:

first = head
while second:
    tmp1 = first.next
    tmp2 = second.next
 
    first.next = second
    second.next = tmp1
 
    first = tmp1
    second = tmp2

One iteration: save the original first.next and second.next before overwriting anything, attach second after first, attach the saved first.next after second, then advance both pointers.

Full trace for [1, 2, 3] (first half) and [5, 4] (reversed second half, from a 5-node input):

Before loop: first=1, second=5. Chains: 1->2->3->null, 5->4->null.

After iteration 1: 1 -> 5 -> 2 -> 3 -> null and 4 -> null. first = 2, second = 4.

After iteration 2: 1 -> 5 -> 2 -> 4 -> 3 -> null. second = null. Loop ends.

The second half terminates the loop because after the split the second half is either equal in length to the first half (even-length input) or one node shorter (odd-length input). The first half always has a node ready when the second half still does.

ListNode first = head;
while (second != null) {
    ListNode tmp1 = first.next;
    ListNode tmp2 = second.next;
    first.next = second;
    second.next = tmp1;
    first = tmp1;
    second = tmp2;
}

The complete O(1) space solution

class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head or not head.next:
            return
 
        # Step 1: find midpoint
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
 
        # Step 2: reverse second half
        second = slow.next
        slow.next = None
        prev = None
        cur = second
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        second = prev
 
        # Step 3: merge alternating
        first = head
        while second:
            tmp1 = first.next
            tmp2 = second.next
            first.next = second
            second.next = tmp1
            first = tmp1
            second = tmp2

public class Solution {
    public void ReorderList(ListNode head) {
        if (head == null || head.next == null) return;
 
        // Step 1: find midpoint
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
 
        // Step 2: reverse second half
        ListNode second = slow.next;
        slow.next = null;
        ListNode prev = null, cur = second;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nxt;
        }
        second = prev;
 
        // Step 3: merge alternating
        ListNode first = head;
        while (second != null) {
            ListNode tmp1 = first.next;
            ListNode tmp2 = second.next;
            first.next = second;
            second.next = tmp1;
            first = tmp1;
            second = tmp2;
        }
    }
}

O(n) time — each of the three passes touches every node at most once. O(1) extra space — only pointer variables.

Complexity comparison

Both run in O(n). The three-step version is not faster — it is better in the sense that it does not allocate memory proportional to input, and it assembles three reusable linked list primitives that appear constantly in other problems.

I would ship the three-step version in any code review. The array approach is fine as a first draft on a whiteboard; I would flag it immediately if someone tried to merge it.

Edge cases and why the code handles them

1 or 2 nodes. The guard if not head or not head.next: return catches both. A single node has no reordering to do; two nodes are already in the required order (L0 -> L1 is the same as L0 -> Ln).

3 nodes [1, 2, 3]. Slow lands on 2. Second half is [3], reversed is still [3]. Merge runs once: 1 -> 3, then 3.next = 2. second becomes null, loop ends. Result: 1 -> 3 -> 2 -> null. The middle node ends up at the tail.

4 nodes [1, 2, 3, 4] (even). Slow lands on 2. Second half is [3, 4], reversed is [4, 3]. Both halves have length 2. The merge loop runs exactly twice and terminates when second is exhausted. Result: 1 -> 4 -> 2 -> 3.

5 nodes [1, 2, 3, 4, 5] (odd). Slow lands on 3. Second half [4, 5] reversed is [5, 4]. First half has 3 nodes, second has 2. The merge loop runs twice, then second is null. Node 3 stays as the tail of the first half and ends up at the end. Result: 1 -> 5 -> 2 -> 4 -> 3.

Missing the sever (slow.next = None). If you omit this line, the first half still has 3 -> 4 -> 5 appended. The merge step then runs into those extra nodes, either producing a corrupted list or an infinite loop depending on the order pointers are overwritten. The sever is not optional.

Wrong slow/fast termination (while fast and fast.next). On [1, 2, 3, 4, 5], this condition lets slow reach node 3 (the true midpoint), so the second half starts from node 4, dropping node 3 from the second half. Node 3 remains attached to the first half as a "lost" tail. The result would be 1 -> 5 -> 2 -> 4 -> 3 still correct in this case because node 3 happens to be the natural tail — but on [1, 2, 3, 4] it would give 1 -> 4 -> 2 -> 3 with node 3 dangling. The while fast.next and fast.next.next condition is the precise one.

The underlying pattern

This problem is a composition of three canonical linked list primitives: midpoint detection (the tortoise-and-hare), in-place reversal, and alternating merge. None of those primitives is invented here; they exist as standalone LeetCode problems. The insight that unlocks Reorder List is recognizing that the operation you want — zip front with back-reversed — is exactly the composition of those three.

That composability is what separates an experienced engineer's approach from a beginner's. A beginner tries to find a single clever loop. An experienced engineer asks: does this problem decompose? And if so, which primitives does it decompose into?

Where this sits in the linked list series

This problem assumes fluency with Reverse Linked List (206) — Step 2 is that problem verbatim. If the reversal logic feels slow to write, practice 206 first.

Middle of the Linked List (876) is Step 1. The while fast.next and fast.next.next termination is not arbitrary; it comes from there.

Merge Two Sorted Lists (21) is structurally similar to Step 3: save both next pointers, rewire, advance. The only difference is that merge uses a value comparison where Step 3 alternates unconditionally.

Palindrome Linked List (234) chains Steps 1 and 2 of this problem — find midpoint, reverse second half — and then compares the two halves value by value. It is the closest sibling: same setup, different final step.

Sort List (148) applies this problem's structure recursively. The midpoint split becomes the divide step of merge sort; the merge step becomes merging two sorted halves. If Steps 1 and 3 here feel natural, Sort List is the next problem to tackle.

Reverse Nodes in k-Group (25) generalizes Step 2: instead of reversing the second half once, you reverse every group of k nodes throughout the entire list. The pointer manipulation is the same three-variable lockstep.