Reorder List
Problem
Given the head of a singly linked list, reorder the list to follow the pattern: first node, last node, second node, second last node, and so on, modifying the list in-place without altering node values.
- The number of nodes in the list is in the range [1, 5 * 10⁴]
- 1 ≤ Node.val ≤ 1000
Example
head = [1,2,3,4][1,4,2,3]The brute-force approach would be to extract all nodes into an array, then reorder by alternating from the front and back, but this requires O(n) extra space. The optimal approach uses the linked list structure directly: first find the middle of the list, reverse the second half, and then merge the two halves by alternating nodes. This approach achieves O(n) time and O(1) space. For example, starting with [1,2,3,4], the middle is at node 2. The second half [3,4] is reversed to [4,3]. Then merging [1,2] and [4,3] alternately produces [1,4,2,3].
Approach
Straightforward Solution
A naive solution extracts all nodes into an array, then uses two pointers to reorder by alternating from front and back. This uses O(n) extra space and is not optimal.
Core Observation
The problem requires rearranging nodes in a specific interleaved order without extra space. The key insight is that the list can be split into two halves, the second half reversed, and then merged alternately to achieve the desired order.
Path to Optimal
The optimal approach uses the fast and slow pointer technique to find the middle of the list in O(n) time. Then, the second half of the list is reversed in-place. Finally, the two halves are merged by alternating nodes from each half. This approach uses O(1) extra space and linear time.
Optimal Approach
Use two pointers to find the middle node, split the list into two halves, reverse the second half in-place, and then merge the two halves by alternating nodes. This achieves the required reordering in O(n) time and O(1) space.
Time
O(n)
Each step—finding the middle, reversing the second half, and merging—traverses the list at most once, resulting in linear time complexity.
Space
O(1)
All operations are done in-place without allocating extra data structures proportional to the input size, using only a fixed number of pointers.
Pattern Spotlight
Linked List (Fast & Slow Pointers + In-place Reversal + Merge)
When reordering a linked list in a pattern involving nodes from both ends, use fast and slow pointers to find the midpoint, reverse the second half in-place to access nodes from the end efficiently, and then merge the two halves by alternating nodes to achieve the desired order without extra space.
Solution
| 1 | class Solution:
|
| 2 | def reorderList(self, head: ListNode) -> None:
|
| 3 | slow, fast = head, head.next
|
| 4 | while fast and fast.next:
|
| 5 | slow = slow.next
|
| 6 | fast = fast.next.next
|
| 7 |
|
| 8 | second = slow.next
|
| 9 | prev = None
|
| 10 | slow.next = None
|
| 11 | while second:
|
| 12 | tmp = second.next
|
| 13 | second.next = prev
|
| 14 | prev = second
|
| 15 | second = tmp
|
| 16 |
|
| 17 | first, second = head, prev
|
| 18 | while second:
|
| 19 | tmp1, tmp2 = first.next, second.next
|
| 20 | first.next = second
|
| 21 | second.next = tmp1
|
| 22 | first, second = tmp1, tmp2 |
| 1 | class Solution { |
| 2 | public void reorderList(ListNode head) { |
| 3 | ListNode slow = head; |
| 4 | ListNode fast = head.next; |
| 5 | |
| 6 | while (fast != null && fast.next != null) { |
| 7 | slow = slow.next; |
| 8 | fast = fast.next.next; |
| 9 | } |
| 10 | |
| 11 | ListNode second = slow.next; |
| 12 | ListNode prev = null; |
| 13 | slow.next = null; |
| 14 | while (second != null) { |
| 15 | ListNode tmp = second.next; |
| 16 | second.next = prev; |
| 17 | prev = second; |
| 18 | second = tmp; |
| 19 | } |
| 20 | |
| 21 | ListNode first = head; |
| 22 | second = prev; |
| 23 | while (second != null) { |
| 24 | ListNode tmp1 = first.next; |
| 25 | ListNode tmp2 = second.next; |
| 26 | first.next = second; |
| 27 | second.next = tmp1; |
| 28 | first = tmp1; |
| 29 | second = tmp2; |
| 30 | } |
| 31 | } |
| 32 | } |
Step-by-Step Solution
Locate the Middle Node Using Fast and Slow Pointers
| 3 | slow, fast = head, head.next
|
| 4 | while fast and fast.next:
|
| 5 | slow = slow.next
|
| 6 | fast = fast.next.next
|
Objective
To find the midpoint of the linked list efficiently in a single pass.
Key Insight
Using two pointers moving at different speeds (fast moves two steps, slow moves one) allows locating the middle node when fast reaches the end. This technique splits the list into two halves without extra space or multiple passes.
Interview Quick-Check
Core Logic
Fast and slow pointers traverse the list simultaneously; when fast reaches the end, slow is at the midpoint, enabling O(n) time middle detection.
State & Boundaries
The loop condition `while fast and fast.next` ensures the slow pointer stops at the node before the start of the second half.
Common Pitfalls & Bugs
Initializing fast to `head.next` instead of `head` ensures correct middle for even-length lists, preventing off-by-one errors.
Reverse the Second Half of the List In-Place
| 8 | second = slow.next
|
| 9 | prev = None
|
| 10 | slow.next = None
|
| 11 | while second:
|
| 12 | tmp = second.next
|
| 13 | second.next = prev
|
| 14 | prev = second
|
| 15 | second = tmp
|
Objective
To reverse the nodes after the midpoint to enable efficient merging from the end.
Key Insight
Reversing the second half transforms the tail portion into a list that can be traversed from what was originally the last node forward. This allows merging nodes alternately from the front and back without extra space or complex indexing.
Interview Quick-Check
Core Logic
In-place reversal uses a pointer to track the previous node and iteratively reverses the next pointers, achieving O(n) time and O(1) space.
State & Boundaries
Setting `slow.next = None` breaks the list into two independent halves, preventing cycles during reversal and merge.
Common Pitfalls & Bugs
Failing to disconnect the first half from the second half before reversal can cause cycles or incorrect merges.
Merge the Two Halves by Alternating Nodes
| 17 | first, second = head, prev
|
| 18 | while second:
|
| 19 | tmp1, tmp2 = first.next, second.next
|
| 20 | first.next = second
|
| 21 | second.next = tmp1
|
| 22 | first, second = tmp1, tmp2 |
Objective
To interleave nodes from the first half and the reversed second half to achieve the final reordered list.
Key Insight
By alternating nodes from the front half and the reversed back half, the algorithm reconstructs the list in the required order without extra space. Temporary pointers store next nodes to avoid losing references during pointer reassignment.
Interview Quick-Check
Core Logic
Alternating merges use temporary pointers to preserve next nodes, ensuring the list is correctly interwoven without losing any nodes.
State & Boundaries
The loop continues until all nodes from the reversed second half are merged, guaranteeing the correct final order.
Common Pitfalls & Bugs
Not storing next pointers before reassignment can cause loss of access to remaining nodes, breaking the list.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
second.next = prevReverse the current node's next pointer to point to prev.
This is the core reversal step that flips the direction of the linked list pointers.
tmp = second.nextStore next node temporarily before changing pointers.
Preserving the next node is essential to continue traversal after pointer reversal.
tmp1, tmp2 = first.next, second.nextStore next nodes of first and second pointers before re-linking.
Preserving next nodes prevents losing access to the remaining list during pointer reassignment.
slow, fast = head, head.nextInitialize slow pointer at head and fast pointer at head.next to find the middle.
Starting fast at head.next ensures that for even-length lists, slow will point to the node just before the midpoint, enabling correct splitting of the list.
slow.next = NoneDisconnect the first half from the second half.
Breaking the link prevents cycles and ensures the two halves are independent for reversal and merging.
first.next = secondLink first node's next to second node.
This inserts a node from the reversed second half after the current first half node, starting the interleaving.
second.next = tmp1Link second node's next to the stored next node of first half.
Completes the interleaving by connecting the second half node to the next node in the first half.
slow = slow.nextMove slow pointer one step forward.
Slow pointer advances at half the speed of fast, so it reaches the middle when fast reaches the end.
fast = fast.next.nextMove fast pointer two steps forward.
Fast pointer moves twice as fast to find the end of the list, enabling slow to find the midpoint in a single pass.
second = slow.nextSet second pointer to the node after slow, marking the start of the second half.
This separates the list into two halves by marking the beginning of the second half for reversal.
while second:Loop while second pointer is not null to reverse the second half.
Iteratively reverses the second half by redirecting next pointers until all nodes are reversed.
prev = secondMove prev pointer to current node.
Prev advances to the new head of the reversed list, maintaining the reversed list's front.
second = tmpAdvance second pointer to the next node to continue reversal.
Moving forward in the original list to reverse all nodes in the second half.
first, second = head, prevInitialize first pointer at head and second pointer at reversed list head.
These pointers track the current nodes in the two halves for merging.
while second:Loop while second pointer is not null to merge nodes alternately.
Ensures all nodes from the reversed second half are merged into the first half.
first, second = tmp1, tmp2Advance first and second pointers to their respective next nodes.
Moves pointers forward to continue merging the remaining nodes.
while fast and fast.next:Loop while fast and fast.next are not null to advance pointers.
This condition ensures the fast pointer can move two steps safely, preventing null reference errors and correctly positioning slow at the midpoint.
prev = NoneInitialize prev pointer to None for reversal.
Prev tracks the reversed list's head as nodes are reversed in-place.
Test Your Understanding
Why is reversing the second half of the list necessary before merging?
Reversing the second half allows direct access to nodes from the end of the original list in forward traversal order, enabling an efficient in-place merge that alternates nodes from the front and back without extra space.
Related Problems
Linked Lists pattern
Don't just read it. Drill it.
Reconstruct Reorder List from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Reorder List drill