The problem
A list runs L₀ → L₁ → … → Lₙ₋₁ → Lₙ. Rearrange its nodes, in place, into L₀ → Lₙ → L₁ → Lₙ₋₁ → L₂ → Lₙ₋₂ → … — first, last, second, second-to-last, and so on.
Only the arrows may change, not the values in the nodes.
Examples
01
- Input
head = [1, 2, 3, 4]
- Output
[1, 4, 2, 3]
02
- Input
head = [1, 2, 3, 4, 5]
- Output
[1, 5, 2, 4, 3]
Constraints
- 1 ≤ number of nodes ≤ 5 × 10⁴
- 1 ≤ Node.val ≤ 1000
The idea
The answer takes alternately from the front half going forward and from the back half going backward. A singly linked list cannot go backward — so reverse the back half first.
Three steps. Find the middle with a slow pointer (one node a step) and a fast one (two a step): when fast reaches the end, slow is halfway. Cut there and reverse the second half. Then weave: one node from the front, one from the reversed back, until the back runs out.
- Time
- O(n) — three passes
- Space
- O(1) — only arrows move
Solution · every language run against every case
class Solution: def reorderList(self, head: Optional[ListNode]) -> None: # 1. Find the middle: fast moves two steps for each one of slow. slow, fast = head, head.next while fast and fast.next: slow, fast = slow.next, fast.next.next # 2. Cut the list in two and reverse the second half. second, slow.next = slow.next, None prev = None while second: second.next, prev, second = prev, second, second.next # 3. Weave them together: one from the front, one from the (reversed) back. first, second = head, prev while second: n1, n2 = first.next, second.next first.next, second.next = second, n1 first, second = n1, n2