Reorder List
The Prompt
You are given the head of a singly linked list. The list can be represented as: `L0 → L1 → … → Ln-1 → Ln`. Reorder the list to be on the following form: `L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …` You may not modify the values in the list's nodes. Only nodes themselves may be changed.
Understanding the Problem
Reordering L0 → L1 → … → Ln into L0 → Ln → L1 → Ln-1 → … means interleaving the list with its own reversed tail. Doing that directly is painful because a singly linked list cannot walk backward to fetch Ln, then Ln-1, on demand.
The insight is decomposition into three subproblems you already know: (1) find the middle with slow/fast pointers, (2) reverse the second half in place, (3) weave the two halves together by alternating nodes. Each piece is a standard O(n)-time, O(1)-space linked-list move.
The Interview Flow
Interviewer
How would you reorder a linked list in this alternating fashion?
Candidate
This looks like it can be broken down into a few steps. It seems I need to merge the first half of the list with the reversed second half.
Interviewer
That's a great observation. Can you outline the steps?
Candidate
Sure. First, I need to find the middle of the linked list. I can do this with the slow and fast pointer technique. Second, I need to reverse the second half of the list. I can use the standard iterative reversal algorithm for this. Third, I need to merge the first half and the reversed second half by weaving them together.
Interviewer
Let's walk through the merge step.
Candidate
I'll have two pointers, one at the head of the first half (`first`) and one at the head of the reversed second half (`second`). I'll loop while the second half is not empty. In each iteration, I'll save the next nodes of both lists. Then, I'll set `first.next = second` and `second.next = first_next`. After that, I'll move my pointers forward: `first = first_next` and `second = second_next`.
Interviewer
That covers all the steps. It's a good combination of several linked list subproblems. Please implement it.
Why does find-middle + reverse + weave produce the target order?
The target sequence alternates between "next node from the front" (L0, L1, L2, …) and "next node from the back" (Ln, Ln-1, …). After splitting at the middle and reversing the second half, the front half emits L0, L1, … in order and the reversed back half emits Ln, Ln-1, … in order — so the weave step just alternates two already-correct streams. The invariant during weaving: everything spliced so far is in final position, and both remaining halves are untouched suffixes.
All three phases touch each node a constant number of times, so the total is O(n) time and O(1) extra space. The tempting alternative — copy nodes into an array and rebuild with two indices — is the same time but O(n) space; the three-phase version is the answer that shows you can rewire pointers safely.
Three-Step Solution: Find Middle, Reverse, Merge
- **Step 1: Find the middle of the list.** Use two pointers, `slow` and `fast`. `slow` moves one step, `fast` moves two. When `fast` reaches the end, `slow` will be at the middle.
- **Step 2: Reverse the second half.** The node after `slow` is the head of the second half. Use the standard iterative algorithm with `prev`, `curr` pointers to reverse this part of the list. Set `slow.next` to `null` to split the list into two.
- **Step 3: Merge the two halves.** Initialize `first = head` and `second` to the head of the reversed second half. Iterate while `second` is not null. Use temporary variables to store `first.next` and `second.next`. Then, interleave the nodes: `first.next = second` and `second.next = tmp1`. Finally, move the pointers forward: `first = tmp1`, `second = tmp2`.
Try it yourself
Write your solution and run it against 2 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function reorderList(head) {
if (!head) return;
// Find middle
let slow = head, fast = head;
while (fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
}
// Reverse second half
let prev = null, curr = slow.next;
while (curr) {
const nextNode = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
}
slow.next = null; // Split the list
// Merge lists
let first = head, second = prev;
while (second) {
const tmp1 = first.next, tmp2 = second.next;
first.next = second;
second.next = tmp1;
first = tmp1;
second = tmp2;
}
}Explanation
Reorder 1 → 2 → 3 → 4 into 1 → 4 → 2 → 3 in three phases.
1Phase 1 — find the middle: slow moves one step while fast moves two. Slow stops at 2, the end of the first half. Split into 1 → 2 and 3 → 4.
2Phase 2 — reverse the second half: 3 → 4 becomes 4 → 3. Now the back of the list can be consumed front-to-back.
3Phase 3 — weave: take 1 from the front, 4 from the back, then 2 from the front. Saved next-pointers keep both halves reachable while splicing.
4The last back node 3 is spliced after 2: final order 1 → 4 → 2 → 3, exactly L0 → Ln → L1 → Ln-1.
Complexity Analysis
TIME
O(n)
SPACE
O(1)
Finished working through this one?
Mark it complete to track it on your Data Structures path.