The problem
Reorder a linked list L0 → L1 → … → Ln into L0 → Ln → L1 → Ln−1 → L2 → …, changing links, not values.
Input: 1 → 2 → 3 → 4 → 5 Output: 1 → 5 → 2 → 4 → 3
Picture it
Picture the train being zipped like a jacket. Step 1: a tortoise (1 step) and a hare (2 steps) find the middle coach. Step 2: reverse the back half, so it now runs from the last coach inward. Step 3: zip the two halves together, alternating a coach from the front half and a coach from the reversed back half.
How to recognise it
- The output alternates between the front and the back of a singly linked list: first, last, second, second-to-last, and so on.
- You can only walk forwards, yet you need the back half in reverse order. Reversing that half turns "walk backwards" into "walk forwards".
- You must relink nodes, not swap values, and the expected solution uses O(1) extra space.
- Up to 5 × 10^4 nodes, so walking to the tail again for every node is too slow.
- The task splits into three moves you may already know: find the middle (fast and slow pointers), reverse a list, and merge two lists.
Start with brute force
Take the nodes one at a time from the front. For each, walk to the end, unhook the last node and insert it right after the current one.
def reorder_brute(head):
curr = head
while curr and curr.next and curr.next.next:
before_last = curr
while before_last.next.next:
before_last = before_last.next
last = before_last.next
before_last.next = None
last.next = curr.next
curr.next = last
curr = last.next
It is correct and uses O(1) extra space, but each walk to the end costs up to n steps, so time is O(n²). For 5 × 10^4 nodes that is roughly 6 × 10^8 steps. Storing all nodes in an array fixes the time (two indices meet in the middle) but costs O(n) space.
From brute force to the idea
- Find the waste. The brute force walks to the tail again and again only because it cannot move backwards. The order it needs from the back half is simply that half reversed.
- Find the middle.
slowmoves one step andfasttwo. The loopwhile fast.next and fast.next.nextstops withslowat the last node of the front half; for odd lengths the front half gets the extra node (1 2 3 | 4 5). - Cut and reverse. Set
slow.next = Noneso the halves are separate lists, then reverse the back half with the usual three-pointer loop (prev,currand the next node, here in one tuple assignment).prevends as the old tail. - Zip. Take
afrom the front half andbfrom the reversed back half. Linka → b, thenb →the next front node, and move both on. Python evaluates the right side ofa.next, a = b, a.nextbefore assigning, so the olda.nextis saved for free. - Stop when the back half runs out. The back half is never longer than the front, so
while bis enough. The front half's last node already ends inNone.
This is the key idea: middle, reverse, merge, each in O(n) time and O(1) space.
The key idea
Find the middle, reverse the second half, merge alternately. O(n) time, O(1) space.
Python solution
def reorder_list(head):
slow = fast = head
while fast.next and fast.next.next: # 1. find the middle
slow, fast = slow.next, fast.next.next
prev, curr = None, slow.next # 2. reverse the back half
slow.next = None
while curr:
curr.next, prev, curr = prev, curr, curr.next
a, b = head, prev # 3. zip the halves
while b:
a.next, a = b, a.next
b.next, b = a, b.nextIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): a walk to the tail for every pair of nodes | O(1): a few references |
| Middle, reverse, zip (shown code) | O(n): three passes, each over at most n nodes | O(1): a fixed number of references, nodes are relinked |
Edge cases
- One node: the middle loop does not run, the back half is empty, and the list is unchanged.
- Two nodes (
1 → 2):slowstays at 1, the back half is just 2, and the list stays1 → 2. - Even length (
1 → 2 → 3 → 4): becomes1 → 4 → 2 → 3. - Odd length (
1 → 2 → 3 → 4 → 5): becomes1 → 5 → 2 → 4 → 3, and node 3 ends withNone. - Empty list: LeetCode guarantees at least one node. The shown code reads
fast.nextstraight away, sohead = NoneraisesAttributeError; addif not head: returnto be safe. - Return value: the function changes the list in place and returns
None, as LeetCode expects.
Common mistakes
- Forgetting
slow.next = None. The front half still runs into the back half, and the zip creates a cycle. - Zipping
while ainstead ofwhile b. The front half can be one node longer, so for odd lengths (and a single node) the last step runsb.nextonNoneand raisesAttributeError. - Writing the zip as separate statements (
a.next = bthena = a.next), which movesaontobinstead of the next front node. - Swapping values instead of relinking nodes.
Decide whether a singly linked list reads the same forwards and backwards (1 → 2 → 2 → 1 is true, 1 → 2 is false), in O(n) time and O(1) extra space. Describe your approach, then write it if you like.
Compare with our answer
Use the same first two moves. Find the middle, reverse the back half, then walk the front and the reversed back side by side, comparing values instead of zipping.
def is_palindrome(head):
slow = fast = head
while fast and fast.next: # slow ends at the middle
slow, fast = slow.next, fast.next.next
prev = None
while slow: # reverse from the middle on
slow.next, prev, slow = prev, slow, slow.next
a, b = head, prev
while b:
if a.val != b.val:
return False
a, b = a.next, b.next
return True
Time O(n), space O(1). It changes the list; reverse the back half again if the caller still needs it.
A strong answer mentions: the fast/slow middle, comparing only until the reversed half runs out, why the odd middle node needs no check, and that the input is modified.
1. For a list of even length, the "twin" of node i is node n − 1 − i. Find the largest sum of twins in O(1) extra space. Which approach fits best?
Reversing the back half lines each node up with its twin in one forward walk: O(n) time, O(1) space. The array and the recursion both use O(n) memory, and walking to each twin is O(n²).
2. Why does the shown code use O(1) extra space, while the array version uses O(n)?
Finding the middle, reversing and zipping each use a fixed number of references (slow, fast, prev, curr, a, b). The middle comes from fast and slow pointers, not a count, and there is no recursion.
3. A learner deletes slow.next = None. What happens for 1 → 2 → 3 → 4?
Without the cut, node 2 still links to node 3, which is also the last node of the reversed back half. The final zip step runs b.next = a with a and b both node 3, so 3 points to itself.
Score 60% or more and the lesson is marked complete.