Coding Interview PatternsReorder List
MediumFast and Slow Pointers
Reorder List
Explanation & Solution
Description
You are given the head of a singly linked list. The list can be represented as:
L0 → L1 → … → Ln-1 → Ln
Reorder the list to be in the following form:
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.
Return the reordered list as an array.
Input:head = [1,2,3,4]
0
1
1
2
2
3
3
4
Output:[1,4,2,3]
0
1
1
4
2
2
3
3
Explanation: The list is reordered from 1→2→3→4 to 1→4→2→3.
Constraints
- The number of nodes in the list is in the range
[0, 5 × 10⁴] 1 <= Node.val <= 1000
Approach
Fast and Slow Pointers pattern
1. Handle Edge Cases
- If the list is empty or has only one node, no reordering is needed — return the list as-is.
2. Find the Middle of the List
- Use two pointers:
slowmoves one step,fastmoves two steps. - When
fastcan no longer advance two steps,slowis at the end of the first half. - Sever the list at the midpoint:
slow.next = null.
3. Reverse the Second Half
- Starting from
slow.next(saved before severing), reverse the linked list in-place. - After reversal,
prevpoints to the head of the reversed second half.
4. Merge Alternating Nodes
- Interleave nodes from the first half and the reversed second half:
first.next = second(insert a node from the back)second.next = tmp1(reconnect to the next node from the front)- Continue until the second half is exhausted.
5. Return the Result
- Traverse the reordered list and collect values into an array.
Key Insight
- This problem combines three classic linked list techniques: finding the middle (slow/fast pointers), reversing a list, and merging two lists.
Time
O(n)each step traverses at most the full list.Space
O(1)all operations are done in-place (excluding the output array).Visualization
Input:
Linked List Traversal
—
Press play to start traversal
Slow (S)Fast (F)Both
7 steps