Reorder List

1. Problem & Core Objective

Given L0 → L1 → … → Ln-1 → Ln, reorder it in place to:

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

Values may not be changed — only the node links.

[1,2,3,4]     →  [1,4,2,3]
[1,2,3,4,5]   →  [1,5,2,4,3]

Constraints: 1 <= n <= 5 × 10^4 · 1 <= Node.val <= 1000

What's actually being tested: whether you can see that a problem with no obvious technique is a composition of three you already know. Nothing here is new — it's find-the-middle, reverse, and merge, run back to back.

2. First-Principles Thought Process

What the target order actually is

Look at [1,2,3,4,5] → [1,5,2,4,3] and read off where the elements come from:

1  5  2  4  3
↑  ↑  ↑  ↑  ↑
front back front back front

It alternates between the front of the list and the back of the list. So the output is an interleaving of:

• the first half read forwards: 1, 2, 3
• the second half read backwards: 5, 4

Why that's hard on a singly linked list

Reading the second half backwards means walking against the next pointers — impossible directly. There are only two ways to get backward access:

1. Store the nodes in an array so you can index from the end — O(n) space.
2. Reverse the second half so backwards becomes forwards — O(1) space.

The second is the intended answer, and it's why question 1 had to come first.

The decomposition

1. Find the middle — slow/fast pointers. fast moves two steps for every one of slow, so when fast reaches the end slow is at the midpoint.
2. Reverse the second half — the exact routine from question 1.
3. Weave — alternate one node from each half.

Each phase is O(n) time and O(1) space, so the whole thing is.

The insight worth stating

Recognising a problem as a composition of known moves is the actual skill here. No step is hard; seeing the three steps is.

3. Solution Paths

Approach 1 — Copy into an array, two pointers (brute force)

public void reorderList(ListNode head) {
    List<ListNode> nodes = new ArrayList<>();
    for (ListNode p = head; p != null; p = p.next) nodes.add(p);

    int i = 0, j = nodes.size() - 1;
    while (i < j) {
        nodes.get(i).next = nodes.get(j);      // front → back
        i++;
        if (i == j) break;                     // odd length: middle node is now last
        nodes.get(j).next = nodes.get(i);      // back → next front
        j--;
    }
    nodes.get(i).next = null;                  // terminate
}

An array gives random access, so the back half is readable directly.

• Time O(n) · Space O(n)

Counter-questions on this approach

⭐ "Why does this need the array at all?"

Purely to read the list backwards. A singly linked list only goes forward, so I materialise the nodes into a structure that supports indexing from the end. The array isn't doing anything algorithmic — it's a workaround for a missing back-pointer.

That reframes the problem: instead of buying random access for O(n) space, I can reverse the second half and read it forwards for free.

⭐ "Why the if (i == j) break; in the middle of the loop?"

Odd-length lists. When i and j meet, that single node is the last one in the output, and it must terminate. Without the break I'd write nodes.get(j).next = nodes.get(i) with i == j — a self-loop, and an infinite list. It's the classic off-by-one in this pattern, and it's why I set next = null explicitly at the end.

"Is O(n) space disqualifying at n = 5 × 10^4?"

No — 50,000 references is trivial. The problem doesn't demand O(1). But the O(1) solution reuses two routines I already have, so it's not more work, and "I can do this without the array" is the answer that demonstrates the pattern.

Approach 2 — Find middle, reverse, weave (optimal)

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

    // 1. find the middle — slow ends on the last node of the first half
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 2. reverse the second half, detaching it from the first
    ListNode second = slow.next;
    slow.next = null;                       // split the list in two
    ListNode prev = null;
    while (second != null) {
        ListNode next = second.next;
        second.next = prev;
        prev = second;
        second = next;
    }

    // 3. weave the two halves
    ListNode first = head, back = prev;
    while (back != null) {
        ListNode f = first.next, b = back.next;
        first.next = back;
        back.next  = f;
        first = f;
        back  = b;
    }
}

Trace — [1,2,3,4]:

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "Why does fast start at head.next rather than head?"

It controls which node slow lands on for even-length lists, and here I need slow to stop on the last node of the first half so that slow.next = null splits evenly.

With fast = head on [1,2,3,4], slow ends on node 3 — giving halves of 3 and 1. With fast = head.next, slow ends on node 2 — halves of 2 and 2. For odd lengths the extra node lands in the first half either way, which is what the target order wants.

It's a one-character difference that silently changes the answer, so I'd state the intent rather than trusting the default.

⭐ "Why must you set slow.next = null?"

To cut the list in two. Without it, the first half's tail still points into the second half, which has just been reversed — so the first half now runs forward into a chain pointing backward, producing a cycle. The weave loop would never terminate.

It's the single most common bug in this problem, and it's silent: the reversal looks right in isolation.

"How does the weave loop know when to stop?"

while (back != null). For even lengths both halves are the same size and they run out together. For odd lengths the first half has one extra node, which is exactly the middle element — it stays at the end with its next already null from the reversal. So the loop condition on back handles both parities without a branch.

"Why save both f and b before rewiring?"

Same reason as question 1 — first.next = back destroys the pointer to the rest of the first half, and back.next = f destroys the pointer to the rest of the second. Both escape routes have to be saved before either assignment.

"Does this mutate the caller's list?"

Yes, entirely, which the signature implies by returning void. The original node order is unrecoverable afterwards.

Comparison

(There's no meaningful middle approach here — you either buy backward access with memory or manufacture it by reversing.)

4. Why the Optimal Wins

Both are O(n) time, so this is entirely about space — and about what the solution demonstrates.

The array version treats "I can't walk backwards" as a constraint to work around by paying memory. The optimal treats it as a constraint to remove: reverse the half you need backwards, and forwards is backwards. Same result, no allocation, and it reuses a routine you already wrote.

The framing worth keeping:

When you need to traverse a singly linked list backwards, reverse the part you need. It converts a missing capability into a routine you already have.

The same move powers Palindrome Linked List and Reverse Nodes in K-Group.

5. Java Prerequisites

Finding the middle — know both variants and what they differ on:

ListNode slow = head, fast = head;         // even n: slow lands on the SECOND middle
ListNode slow = head, fast = head.next;    // even n: slow lands on the FIRST middle
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }

The fast != null && fast.next != null order matters: short-circuiting prevents fast.next.next from throwing when fast is the last node.

Splitting

ListNode second = slow.next;
slow.next = null;              // without this, the halves stay connected

Weaving two chains

ListNode f = first.next, b = back.next;    // save both escape routes FIRST
first.next = back;
back.next  = f;
first = f;
back  = b;

6. Interview Communication Guide

Clarifying questions: In place, or may I return a new list (in place, void)? Can I modify values or only links (links only)? Is O(1) space required (ask — it changes the approach)? Can the list be a single node (yes; return immediately)?

The pitch

"Reading the target order off an example, it alternates front, back, front, back — so the output is the first half forwards interleaved with the second half backwards.

The problem is that a singly linked list can't be walked backwards. I can buy that with an array of node references, which is O(n) space — or I can reverse the second half so that backwards becomes forwards, which is O(1).

So it decomposes into three routines I already have. Find the middle with slow/fast pointers. Reverse the second half — that's question 1 verbatim. Then weave, taking one node from each.

Two details I'd be careful about. fast starts at head.next so that on an even-length list slow lands on the last node of the first half, giving an even split. And I must set slow.next = null to actually detach the halves — otherwise the first half runs into the reversed second half and the weave loop spins forever.

Each phase is O(n) and O(1), so the whole thing is O(n) time and O(1) space."

Edge cases to volunteer:

The odd-length cases are the ones to name. They're where the two halves are different sizes, and where while (back != null) silently does the right thing — worth saying out loud that you checked it rather than got lucky.

7. Follow-Up Questions — Modified Constraints

⭐ "Restore the original order afterwards."

Run the inverse: unweave into two lists by taking alternate nodes, reverse the second one back, and reattach. Each step is invertible because none of them lost information — nothing was allocated or discarded. Worth saying, because it shows the transformation is a permutation, not a rebuild.

"Interleave from the back first: Ln → L0 → Ln-1 → L1 → …."

Same three phases, but start the weave from the reversed half. The only change is which pointer leads in the weave loop.

"What if the list were doubly linked?"

Phase 1 and 2 collapse — you can walk backwards from the tail directly, so there's nothing to reverse. It becomes a single weave with a pointer from each end converging, much like the two-pointer array problems in Section 2.

"Do it for a list of 10 million nodes."

Unchanged — it's already O(1) space and a constant number of linear passes. This is precisely where the array version would hurt: 10 million object references is ~80 MB of pointers on a 64-bit JVM, on top of the nodes themselves.

"Can you do it in a single pass?"

No. You cannot know where the middle is without reaching the end, and you cannot read the back half until you've reached it. Three passes is the floor for O(1) space. Naming the lower bound is better than vaguely promising to optimize further.

"What if you had to do this repeatedly on a list that keeps growing?"

Maintain the middle pointer incrementally as nodes are appended — advance it every second insertion — which removes phase 1. Or switch to a deque-backed structure where both ends are O(1) and the whole problem dissolves. The right answer depends on the read/write ratio.