Appearance
4.9.3 — Reorder List
LeetCode 143 · Medium · ★ Blind 75
The problem
You are given the head of a linked list L_0 \to L_1 \to \dots \to L_n. Rearrange it into L_0 \to L_n \to L_1 \to L_{n-1} \to L_2 \to \dots. In words: the first node, then the last node, then the second node, then the second-to-last, and so on. You must re-link the nodes themselves, not just swap their values. Nothing is returned; the list is changed in place.
1 → 2 → 3 → 4 becomes 1 → 4 → 2 → 3
1 → 2 → 3 → 4 → 5 becomes 1 → 5 → 2 → 4 → 3The list has between 1 and 50,000 nodes.
What the problem is really asking
Imagine folding the list in half like a strip of paper, so the end lands on top of the start, and then reading the layers alternately.
The trouble is that the target order needs the last node second, the second-to-last fourth, and so on. A singly linked list can only be walked forwards. There is no cheap way to reach the back.
So the real question is: how do you make the back half of the list reachable from the front? The answer is to reverse it.
The brute force, and where it wastes work
Without extra memory, the direct approach is: take the first node, walk the whole list to find the last node, link them, then repeat from the second node.
Finding the last node takes about n steps, the second-to-last n - 1, and so on. That adds up to about \frac{n^2}{2} steps, over a billion for 50,000 nodes.
The waste in one sentence: it walks almost the whole list again every time it needs the next node from the back.
The idea
Three techniques you have already met, used one after another.
- Find the middle with a slow pointer and a fast pointer.
- Reverse the second half, using the loop from 4.9.1. Now the back of the list can be walked starting from its last node.
- Weave the two halves together, taking one node from each in turn.
1 → 2 → 3 → 4 → 5 → 6
split: 1 → 2 → 3 4 → 5 → 6
reverse: 1 → 2 → 3 6 → 5 → 4
weave: 1 → 6 → 2 → 5 → 3 → 4Finding the middle with two speeds
Start two pointers at the head. Move slow one node per step and fast two nodes per step. When fast reaches the end, slow has gone exactly half as far, so it is at the middle.
python
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.nextOn a list with an even number of nodes there are two middles. This loop stops slow on the second one. For 1 → 2 → 3 → 4, slow ends on node 3. The second half is then everything after slow, which is just node 4. That leaves the first half one node longer than the second half or the same length, which is what the weave needs.
Do not memorise which middle you get. Trace a four-node list in your head before you commit. It takes five seconds, and it removes the most common source of off-by-one bugs in linked-list problems.
The solution
python
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
if not head or not head.next: # (1)
return
slow, fast = head, head # (2)
while fast and fast.next:
slow = slow.next
fast = fast.next.next
second = slow.next # (3)
slow.next = None # (4)
prev = None # (5)
while second:
nxt = second.next
second.next = prev
prev = second
second = nxt
second = prev # (6)
first = head # (7)
while second: # (8)
f_next, s_next = first.next, second.next # (9)
first.next = second # (10)
second.next = f_next # (11)
first, second = f_next, s_next # (12)ts
function reorderList(head: ListNode | null): void {
if (!head || !head.next) return; // (1)
let slow = head, fast: ListNode | null = head; // (2)
while (fast && fast.next) {
slow = slow.next!;
fast = fast.next.next;
}
let second = slow.next; // (3)
slow.next = null; // (4)
let prev: ListNode | null = null; // (5)
while (second) {
const nxt: ListNode | null = second.next;
second.next = prev;
prev = second;
second = nxt;
}
second = prev; // (6)
let first: ListNode | null = head; // (7)
while (second) { // (8)
const fNext = first!.next, sNext: ListNode | null = second.next; // (9)
first!.next = second; // (10)
second.next = fNext; // (11)
first = fNext; // (12)
second = sNext;
}
}Line by line
(1) Lists of 0 or 1 node are already in the right order.
(2) Find the middle. slow moves one step, fast moves two. The loop stops when fast has no room for two more steps. As explained above, slow ends on the middle node, or the second of two middles.
(3) The second half starts just after slow.
(4) Cut the list in two. This is the line people forget. Without it, the last node of the first half still points into the second half. After step 2 reverses the second half, that leftover pointer creates a loop, and the list never ends. The two halves must be fully separated before they are woven.
(5) Reverse the second half. This is exactly the loop from 4.9.1: save the next node, turn the arrow back, step forward.
(6) prev is the head of the reversed second half, which was the last node of the original list.
(7) first walks the first half from the original head.
(8) Loop while the second half has nodes. The second half is never longer than the first, so it always runs out first. If we looped on first instead, the last step would try to read .next from None and crash.
(9) Save both next nodes. The moment line (10) runs, the old first.next is overwritten. Same rule as reversing: save the way forward before you change a pointer.
(10) The first-half node points to the second-half node.
(11) The second-half node points to the next first-half node.
(12) Step both forward to the saved nodes.
Trace
Take 1 → 2 → 3 → 4.
Step 1, find the middle. slow ends on node 3.
Steps 3 and 4, cut. second is node 4. Node 3 now points to None. The halves are 1 → 2 → 3 and 4.
Step 5, reverse. A single node reversed is still 4.
Step 8 onwards, weave.
| Round | first | second | Saved f_next, s_next | Links made |
|---|---|---|---|---|
| 1 | 1 | 4 | 2, None | 1 → 4, 4 → 2 |
| 2 | 2 | None | — | loop ends |
Node 2 still points to node 3, and node 3 points to None. The result is 1 → 4 → 2 → 3. ✓
Now 1 → 2 → 3 → 4 → 5. slow ends on 3. The halves are 1 → 2 → 3 and 4 → 5, reversed to 5 → 4. The weave makes 1 → 5 → 2 → 4 → 3. ✓
Complexity, derived
Time. Finding the middle walks about n/2 steps. Reversing the second half walks about n/2 nodes. Weaving walks about n/2 rounds. That is about 1.5n steps in total, which is O(n).
Space. A handful of pointer variables, no lists and no recursion. So the extra memory is O(1).
The easy alternative
Put every node into an array, then walk it from both ends and re-link.
python
nodes = []
node = head
while node:
nodes.append(node)
node = node.next
i, j = 0, len(nodes) - 1
while i < j:
nodes[i].next = nodes[j] # front points to back
i += 1
if i == j:
break
nodes[j].next = nodes[i] # back points to the next front
j -= 1
nodes[i].next = None # the last node in the new order ends the listThis is O(n) time and O(n) memory. It is much easier to get right. It is a perfectly good first answer if you say the memory cost out loud and then offer the O(1) version as the improvement.
Edge cases
- One node. Line (1) returns.
- Two nodes, like
1 → 2.slowends on 2, the second half is empty, and the list stays1 → 2, which is correct. - Three nodes, like
1 → 2 → 3.slowends on 2. The halves are1 → 2and3. The weave makes1 → 3 → 2.
Variations you will meet
The three pieces here are the whole toolkit for this chapter.
- Palindrome Linked List. Find the middle, reverse the second half, and compare the two halves node by node.
- Sort List. Find the middle, sort each half, and merge them with 4.9.2. That is merge sort on a list.
- Split Linked List in Parts. Cut a list into
knearly equal pieces.
The general lesson: a singly linked list cannot be walked backwards, so when a problem needs the back, reverse that part.
What the interviewer will push on
"Why do you cut the list at the middle?" Otherwise the first half still points into the second half, and reversing creates a loop.
"Which middle does your loop find?" Know it, and prove it by tracing a four-node list.
"Why does the weave loop on the second half?" It is never longer, so it always finishes first.
"Can you do it without extra memory?" Yes, this version. Offer the array version first, since it is easier, then improve it.
One thing to volunteer: name the three steps before you write any code: "find the middle, reverse the second half, weave". Then write them one at a time. This problem punishes people who start typing before they have the plan.
Next: 4.9.4 Remove Nth Node From End of List. Two pointers again, but now with a fixed gap between them.