#143
Reorder List
Medium Middle + reverse + weave
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Reorder L0 → L1 → … → Ln into L0 → Ln → L1 → Ln−1 → … in place.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: first, last, second, second-last…
Why this works: split at the middle, reverse the second half, then weave the halves together.
Example: 1→2→3→4→5
halves 1→2→3 and 4→5 → reversed 5→4weave: 1→5→2→4→3
✦Hints open one at a time
Split the list at the middle.
Reverse the second half.
Weave the two halves together one node at a time.
↗Approach
Combine three basic routines: find middle (slow/fast), reverse the second half after cutting, then alternately link nodes from the first and the reversed second half.
</>Solution (Java)
/**
* class ListNode { int val; ListNode next; } // provided by LeetCode
*/
class Solution {
public void reorderList(ListNode head) {
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode second = reverse(slow.next);
slow.next = null; // cut
ListNode first = head;
while (second != null) { // weave
ListNode n1 = first.next, n2 = second.next;
first.next = second;
second.next = n1;
first = n1;
second = n2;
}
}
private ListNode reverse(ListNode cur) {
ListNode prev = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
}!Common mistake
Not cutting the first half (mid.next = null), which creates a cycle.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Linked List
🎬 Episodes 40–45: video coming soon