Reorder List: Find the Middle, Reverse, and Weave
Solve LeetCode Reorder List in O(n) time and O(1) space by finding the middle, reversing the second half, and merging both halves alternately.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Reorder List looks like it wants you to shuffle nodes randomly, but the target pattern is precise: pull one node from the front, then one from the back, then front, then back, until the list is consumed. The trick is that a singly linked list only lets you walk forward — so grabbing "the node from the back" repeatedly seems to demand O(n) walks each time.
The elegant answer isn't one clever loop. It's three well-known linked-list techniques stitched together: find the middle with fast/slow pointers, reverse the second half in place, then merge the two halves alternately. Each piece is a classic on its own. Reorder List is where they combine.
The problem
Given the head of a singly linked list L0 → L1 → … → Ln-1 → Ln, reorder it in place to interleave the front and back:
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
You may not change node values — only rewire the next pointers. Return nothing; the reordering is done on the original list.
Input: 1 → 2 → 3 → 4 → 5
Output: 1 → 5 → 2 → 4 → 3
Input: 1 → 2 → 3 → 4
Output: 1 → 4 → 2 → 3Read the output pattern carefully: the first node stays first, the last node moves to second, the second node stays third, and so on. It is exactly the sequence you'd produce by alternately taking from the head of the original list and the head of the reversed tail.
The brute force baseline
The most direct approach copies every node into an array so you get random access, then walks two pointers inward from both ends, relinking as you go.
function reorderList(head) {
if (!head) return;
const nodes = [];
for (let node = head; node; node = node.next) nodes.push(node);
let i = 0, j = nodes.length - 1;
while (i < j) {
nodes[i].next = nodes[j];
i++;
if (i === j) break; // pointers met — stop
nodes[j].next = nodes[i];
j--;
}
nodes[i].next = null; // terminate the new list
}This is correct and runs in O(n) time. The cost is the array: O(n) extra space to hold references to all nodes. For an interview, storing the whole list to fake random access is the move you're expected to improve on — a linked list problem usually rewards an in-place, constant-space solution.
The key insight
You can't cheaply reach the back of a singly linked list. But you can cheaply reach the middle, and you can reverse a chain of nodes in place. So instead of reaching backward n times, reverse the second half once — now its nodes come out back-to-front simply by walking forward.
That reframes the whole problem into three linear phases:
- Find the middle so you can split the list into a front half and a back half.
- Reverse the back half in place, so its last node becomes its new head.
- Merge alternately — take one node from the front half, one from the reversed back half, repeat.
None of these needs random access, and none needs extra storage proportional to n. Three passes, each O(n), each using O(1) space.
The optimal solution
This is the exact algorithm the visualizer traces. Note the middle-finding step starts fast at head.next (not head) — that lands slow on the end of the first half, which is where you want to cut.
function reorderList(head) {
if (!head || !head.next) return;
// 1. Find middle (slow ends on the last node of the first half)
let slow = head, fast = head.next;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
// 2. Reverse second half
let curr = slow.next;
slow.next = null; // cut the list into two halves
let prev = null;
while (curr) {
let nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
// 3. Merge alternating (l2 is the reversed second half)
let l1 = head, l2 = prev;
while (l2) {
let t1 = l1.next, t2 = l2.next;
l1.next = l2;
l2.next = t1;
l1 = t1;
l2 = t2;
}
}Three details make it work. slow.next = null severs the first half so it has a clean tail. After reversal, prev — not curr — points at the new head of the reversed half. And the merge loop stops on l2, because the reversed second half is always the same length or one shorter than the first half, so once l2 is exhausted the first half is already correctly terminated.
Walkthrough
Tracing 1 → 2 → 3 → 4 → 5. Nodes are labeled by value; the middle finder uses slow/fast, reversal uses curr/prev, merge uses l1/l2.
| Phase | Step | Pointers | List state |
|---|---|---|---|
| Find middle | init | slow=1, fast=2 | 1 2 3 4 5 |
| Find middle | advance | slow=2, fast=4 | 1 2 3 4 5 |
| Find middle | advance | slow=3, fast=null | fast walked off the end |
| Split | cut | slow=3 | first: 1 2 3 · second: 4 5 |
| Reverse | flip 4 | prev=4 | reversed so far: 4 |
| Reverse | flip 5 | prev=5 | reversed: 5 4 |
| Merge | weave | l1=1, l2=5 | result: 1 5 |
| Merge | weave | l1=2, l2=4 | result: 1 5 2 4 |
| Merge | l2 exhausted | l2=null | leftover 3 already attached → 1 5 2 4 3 |
slow lands on node 3, the last node of the first half. Cutting there gives [1,2,3] and [4,5]. Reversing [4,5] yields [5,4]. The merge then interleaves 1,5,2,4 and the trailing 3 — which was never detached from the first half — stays put as the final node. Result: 1 → 5 → 2 → 4 → 3.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Array + two pointers | O(n) | O(n) | one pass to buffer nodes, one to rewire; array holds n refs |
| Middle + reverse + merge | O(n) | O(1) | three sequential linear passes, only a handful of pointers |
Finding the middle is one pass. Reversing the second half touches each of its nodes once. Merging touches each remaining node once. Three passes over at most n nodes is still O(n) total, and every phase rewires pointers with a fixed set of variables — no allocation that grows with input size.
Common mistakes
- Starting
fastat the wrong node. Withfast = head.next,slowstops on the last node of the first half — exactly the cut point. Startingfast = headshifts whereslowlands for even-length lists and breaks the split. - Forgetting
slow.next = null. If you don't sever the first half, its old tail still points into the second half, and after merging you'll create a cycle. Traversing the result then loops forever. - Merging on
l1instead ofl2. The reversed second half is the shorter (or equal) side. Loop whilel2is non-null; the first half's leftover node is already linked, so no extra cleanup is needed. - Losing the
nextpointer during reversal or merge. Both loops must stash the next node (nextTemp,t1/t2) before rewiring, or you'll orphan the rest of the list. - Skipping the length ≤ 2 guard. A single node or empty list needs no work; the
!head || !head.nextcheck avoids dereferencing null.
Where this pattern shows up next
Reorder List is really three sub-problems in a trench coat. Master each and this one becomes assembly:
- Reverse Linked List — the exact in-place
prev/curr/nextTempreversal used in phase two. - Linked List Cycle — the fast/slow pointer technique that powers the middle-finding phase.
- Linked List Cycle II — fast/slow pointers pushed further, to locate where a cycle begins.
- Palindrome Linked List — the closest cousin: find the middle, reverse the second half, then compare instead of merge.
You can also step through Reorder List interactively to watch the three phases fire one at a time — pointer moves, the reversal flipping links, and the alternating weave.
FAQ
Why reverse the second half instead of using a stack?
A stack of the back-half nodes would also give you last-in-first-out access, but it costs O(n) extra space. Reversing the second half in place achieves the same "read the tail backward" effect using only a few pointer variables, keeping the solution at O(1) space. Since reversal is a standard linked-list move you already know, it's the more idiomatic and memory-efficient choice.
How does the fast/slow pointer find the middle?
The fast pointer moves two nodes per step while slow moves one. By the time fast runs off the end of the list, slow has covered exactly half the distance, landing at or near the middle. Starting fast at head.next tunes it so slow stops on the last node of the first half, which is precisely where you want to split. It finds the midpoint in one pass without ever computing the list's length.
What is the time and space complexity of Reorder List?
Time is O(n): finding the middle, reversing the second half, and merging are each a single linear pass, and three linear passes still total O(n). Space is O(1): the whole reordering rewires next pointers in place using a fixed number of variables (slow, fast, curr, prev, l1, l2, and temporaries), with no array or stack that grows with the input.
Why does the merge loop stop on l2 and not l1?
After splitting at the midpoint, the first half is always the same length as the second half or one node longer (for odd-length lists). So the reversed second half, l2, is the side that empties first. Looping while l2 is non-null weaves in every back-half node; the first half's final leftover node is already attached from the previous step and correctly terminates the list, so no extra handling is required.
Does this work for even-length lists?
Yes. For an even list like 1 → 2 → 3 → 4, the middle finder splits it into [1,2] and [3,4]. Reversing the second half gives [4,3], and merging produces 1 → 4 → 2 → 3. Both halves are the same length, l2 and l1 exhaust together, and the loop ends cleanly with a fully reordered list.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.