Reorder List
Rearrange a list into first, last, second, second-to-last, ... in place, by finding the middle, reversing the second half, and zipping the halves together.
- Combining patterns
- Fast and slow pointers
- Reversing a linked list
Before this, know: Reverse Linked List, Fast and slow pointers (Linked List Cycle)
You get head, the first node of a linked list L0 → L1 → … → Ln. Rearrange it to
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
that is: first, last, second, second-to-last, and so on, like shuffling a deck by alternately taking from the top and the bottom. Change the links, not the values, and do it in place: the function returns nothing.
The rules that matter:
- Up to 50,000 nodes. Lists with 0, 1 or 2 nodes stay exactly as they are.
- You may not just swap values; you must rewire the nodes.
- The answer is checked by walking the list from
headafter your function runs.
Look at the target again: 1, 5, 2, 4, 3. The odd positions are 1, 2, 3
(the first half, in order). The even positions are 5, 4 (the second half,
backwards). So the job breaks into three smaller jobs, each one a pattern
you already know:
- Find the middle, with slow and fast pointers (like Linked List Cycle).
- Reverse the second half, with prev / curr / next (like Reverse Linked List).
- Merge the two halves, taking one node from each in turn (like Merge Two Sorted Lists, but alternating instead of comparing).
Pause and think
First half: 1 → 2 → 3. Second half 4 → 5 → 6, reversed: 6 → 5 → 4.
Zip them, one from each: 1 → 6 → 2 → 5 → 3 → 4. Check against the rule: first
(1), last (6), second (2), second-to-last (5), third (3), third-to-last (4). ✓
A linked list can’t jump to “the last node”, but an array can. So copy every
node (not just its value) into an array, then use two indexes: i from the
front and j from the back. Link nodes[i] → nodes[j] → nodes[i + 1] → …
until they meet. The node where they meet is the new tail.
Brute force: an array of nodes, zipped from both ends
head = [1, 2, 3, 4]
- 10
- nodes[i] (front)
- nodes[j] (back)
- Link just changed
- Done
Copy node 1 into the array. Arrays let us jump to any position, which a linked list can't do.
Which line is running?
function reorderList(head) { const nodes = []; let node = head; while (node !== null) { // copy every node into an arrayRunning now: nodes.push(node); node = node.next; } let i = 0; let j = nodes.length - 1; while (i < j) { nodes[i].next = nodes[j]; // front -> back i++; if (i === j) break; nodes[j].next = nodes[i]; // back -> next front j--; } if (nodes.length > 0) nodes[i].next = null; // the middle node is the new tail}Array of nodes + two indexes
function reorderList(head) { const nodes = []; let node = head; while (node !== null) { // copy every node into an array nodes.push(node); node = node.next; } let i = 0; let j = nodes.length - 1; while (i < j) { nodes[i].next = nodes[j]; // front -> back i++; if (i === j) break; nodes[j].next = nodes[i]; // back -> next front j--; } if (nodes.length > 0) nodes[i].next = null; // the middle node is the new tail}def reorder_list(head): nodes = [] node = head while node is not None: # copy every node into a list nodes.append(node) node = node.next i, j = 0, len(nodes) - 1 while i < j: nodes[i].next = nodes[j] # front -> back i += 1 if i == j: break nodes[j].next = nodes[i] # back -> next front j -= 1 if nodes: nodes[i].next = None # the middle node is the new tailThe time is fine: O(n). But the array holds a reference to every node: O(n) extra memory, 50,000 slots for a 50,000-node list. The interviewer will ask for O(1) extra space, and that’s where the three-phase solution comes in.
Many medium linked-list problems aren’t new ideas at all. They’re two or three small patterns run one after another. The skill is spotting the pieces.
Pattern
Combining patterns
Use it when: the target shape mixes the front and the back of a list, and you need O(1) space.
Signal words
- “reorder”
- “L0 → Ln → L1”
- “palindrome linked list”
- “in place”
- “first and last alternately”
- Phase 1, find the middle.
slowandfaststart at the head. Whilefastcan take 2 more steps, moveslow1 andfast2.slowstops at the end of the first half. - Phase 2, reverse the second half. Cut after the middle (
slow.next = null), then reverse the nodes that came after it.prevends up as the head of the reversed half. - Phase 3, merge alternately.
firstwalks the first half,secondthe reversed half. Save bothnexts, linkfirst → second → (old first.next), and move on. Stop whensecondruns out.
The bar above the picture tells you which phase is running. In phase 2 the second half drops onto its own row and its arrows flip. In phase 3 it’s redrawn left to right so you can watch the zip zig-zag between the rows. The final step lays the answer out on one row.
Three phases, in place
head = [1, 2, 3, 4, 5]
- Phase 1 (current): Find the middle
- Phase 2: Reverse the second half
- Phase 3: Merge, alternating
- slow
- 1node
- fast
- 1node
- slow / curr / first
- fast / second
- First half (waiting)
- Link just changed
- Link just cut
- In its final place
Goal: [1, 2, 3, 4, 5] → first, last, second, second-to-last, ... We do it in 3 phases. Phase 1 finds the middle: slow and fast both start at the head.
Which line is running?
function reorderList(head) { if (head === null || head.next === null) return; // Phase 1: find the middleRunning now: let slow = head; let fast = head; while (fast.next !== null && fast.next.next !== null) { slow = slow.next; fast = fast.next.next; } // Phase 2: reverse the second half let prev = null; let curr = slow.next; slow.next = null; // cut the list in two while (curr !== null) { const next = curr.next; curr.next = prev; prev = curr; curr = next; } // Phase 3: merge the two halves, alternating let first = head; let second = prev; while (second !== null) { const tmp1 = first.next; const tmp2 = second.next; first.next = second; second.next = tmp1; first = tmp1; second = tmp2; }}Middle, reverse, merge
function reorderList(head) { if (head === null || head.next === null) return; // Phase 1: find the middle let slow = head; let fast = head; while (fast.next !== null && fast.next.next !== null) { slow = slow.next; fast = fast.next.next; } // Phase 2: reverse the second half let prev = null; let curr = slow.next; slow.next = null; // cut the list in two while (curr !== null) { const next = curr.next; curr.next = prev; prev = curr; curr = next; } // Phase 3: merge the two halves, alternating let first = head; let second = prev; while (second !== null) { const tmp1 = first.next; const tmp2 = second.next; first.next = second; second.next = tmp1; first = tmp1; second = tmp2; }}def reorder_list(head): if head is None or head.next is None: return # Phase 1: find the middle slow, fast = head, head while fast.next is not None and fast.next.next is not None: slow = slow.next fast = fast.next.next # Phase 2: reverse the second half prev, curr = None, slow.next slow.next = None # cut the list in two while curr is not None: nxt = curr.next curr.next = prev prev = curr curr = nxt # Phase 3: merge the two halves, alternating first, second = head, prev while second is not None: tmp1, tmp2 = first.next, second.next first.next = second second.next = tmp1 first, second = tmp1, tmp2Python returns on its own line (line 3) and assigns pairs on one line (slow, fast = head, head),
so the line numbers drift; both are given below. On LeetCode the method is
def reorderList(self, head) -> None inside class Solution: it changes the list
and returns nothing.
- JS 2 / Py 2–3: 0 or 1 node: nothing to do. (2 nodes also come out unchanged, and the general code handles them correctly.)
- JS 5–10 / Py 6–9, phase 1: the loop condition
fast.next && fast.next.nextstopsslowat the first middle for even lengths (2 in[1, 2, 3, 4]). That keeps the first half the same size as, or one bigger than, the second half. - JS 13–15 / Py 12–13:
currstarts after the middle, andslow.next = nullcuts the list in two. Without the cut, the first half would still lead into the second, and phase 3 would build a loop. - JS 16–21 / Py 14–18, phase 2: the standard reversal. Afterwards
previs the head of the reversed second half. - JS 24–25 / Py 21:
firstwalks the first half,secondthe reversed second half. - JS 26 / Py 22: the second half is never longer than the first, so we stop when it runs out.
- JS 27–28 / Py 23: save both next nodes before rewiring. This is the
“save
nextfirst” rule again, twice. - JS 29–30 / Py 24–25: slot
secondin betweenfirstand the oldfirst.next. - JS 31–32 / Py 26: move both pointers on.
head = [1, 2, 3, 4, 5]:
| phase | what happens | first half | second half | result so far |
|---|---|---|---|---|
| 1 | slow 1→2→3, fast 1→3→5; fast.next is null: stop | middle = 3 | ||
| 2 | cut after 3; reverse 4 → 5 | 1 → 2 → 3 | 5 → 4 | |
| 3 | first = 1, second = 5: link 1 → 5 → 2 | 2 → 3 | 4 | 1 → 5 → 2 |
| 3 | first = 2, second = 4: link 2 → 4 → 3 | 3 | (empty) | 1 → 5 → 2 → 4 → 3 |
| done | second is null: stop | 1 → 5 → 2 → 4 → 3 |
Node 3, the middle, never gets touched in phase 3: it was the end of the first half (pointing to null since the cut), and it stays the last node.
Array of nodes
Time
O(n)
One pass to copy, one pass of i and j toward each other.
Space
O(n)
The array stores a reference to every node.
Middle, reverse, merge
Time
O(n)
Phase 1 walks half the list, phase 2 reverses half, phase 3 visits every node once: about 2n steps, still O(n).
Space
O(1)
A handful of pointers (slow, fast, prev, curr, first, second, tmp1, tmp2).
What to say out loud:
- “The odd positions are the first half in order; the even positions are the second half reversed.”
- “So: find the middle with slow/fast, cut, reverse the second half, then merge alternately.”
- “Each phase is O(n) time and O(1) space.”
- “Edge cases: 0, 1, 2 nodes, and odd vs even length.”
- Name the phases before coding; it shows you see the structure.
Likely follow-ups:
- “Can you do it with a stack instead?” Yes (push all nodes, pop to get the back ones), but that’s O(n) space, like the array.
- “Check whether a linked list is a palindrome in O(1) space.” (LeetCode 234) Same first two phases, then compare the halves instead of merging.
Related problems:
- Reverse Linked List, Linked List Cycle and Merge Two Sorted Lists: the three building blocks.
- The combining patterns section of the week overview.