LeetCode · #143
Reorder List Solution
Reorder L₀→L₁→…→Lₙ to L₀→Lₙ→L₁→Lₙ₋₁→L₂→Lₙ₋₂→… in-place.
01
Section One · Problem
Problem Statement
Given the head of a singly linked list L₀→L₁→…→Lₙ₋₁→Lₙ, reorder it to L₀→Lₙ→L₁→Lₙ₋₁→L₂→Lₙ₋₂→…. You may not modify node values — only change the node links.
Example
Input: 1 → 2 → 3 → 4 → 5 Output: 1 → 5 → 2 → 4 → 3
Constraints
• 1 ≤ number of nodes ≤ 5 × 10⁴ • 1 ≤ Node.val ≤ 1000
02
Section Two · Approach 1
Array + Rebuild — O(n) space
Store all nodes in an array. Use two pointers (front and back) to relink in the desired order. Correct but O(n) extra space.
Problem: O(n) space for the array. We can achieve O(1) space by combining three linked-list primitives: find-middle, reverse, and merge.
03
Section Three · Approach 2
Three-Step In-Place — O(n) time, O(1) space
The reordered list interleaves the first half with the reversed second half. Three steps: (1) find the middle, (2) reverse the second half, (3) merge alternating.
💡 Mental model: Take a deck of cards 1-2-3-4-5. Split it at the middle: [1,2,3] and [4,5]. Reverse the second pile: [5,4]. Now interleave: take from first, then second — 1,5,2,4,3. That's the reordered list.
Algorithm
- Step 1 — Find middle: Use slow/fast pointers. When fast reaches the end, slow is at the middle.
- Step 2 — Reverse second half: Reverse the list starting from
slow.next. Cut the first half by settingslow.next = null. - Step 3 — Merge alternating: Take one node from the first half, then one from the reversed second half, alternating.
🎯 Three classic sub-problems combined:
- This problem is a composition of LC 876 (Middle of Linked List), LC 206 (Reverse Linked List), and LC 21 (Merge Two Sorted Lists) — but with alternating instead of sorted merge.
- Master each primitive first.
04
Section Four · Trace
Visual Walkthrough
Trace: 1 → 2 → 3 → 4 → 5:
Three-step reorder — split, reverse, merge
05
Section Five · Implementation
Code — Java & Python
Java — Three-step in-place
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
// Step 1: Find middle ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Step 2: Reverse second half ListNode second = slow.next;
slow.next = null; // cut first half ListNode prev = null;
while (second != null) {
ListNode next = second.next;
second.next = prev;
prev = second;
second = next;
}
second = prev; // new head of reversed half // Step 3: Merge alternating ListNode first = head;
while (second != null) {
ListNode tmp1 = first.next, tmp2 = second.next;
first.next = second;
second.next = tmp1;
first = tmp1;
second = tmp2;
}
}
}
Python — Three-step in-place
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
if not head or not head.next: return # Step 1: Find middle
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Step 2: Reverse second half
second = slow.next
slow.next = None
prev = None while second:
second.next, prev, second = prev, second, second.next
second = prev
# Step 3: Merge alternating
first = head
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2
06
Section Six · Analysis
Complexity Analysis
| Approach | Time | Space | Trade-off |
|---|---|---|---|
| Array + Rebuild | O(n) | O(n) | Simple but extra memory |
| Three-step ← optimal | O(n) | O(1) | Find middle + reverse + merge |
07
Section Seven · Edge Cases
Edge Cases & Pitfalls
| Case | Input | Why It Matters |
|---|---|---|
| Single/two nodes | 1 or 1→2 | Already in correct order — nothing to do. |
| Even length | 1→2→3→4 | Split: [1,2] and [4,3]. Merge: 1→4→2→3. |
| Odd length | 1→2→3→4→5 | First half has extra node. Merge leaves middle node (3) at end. |
⚠ Common Mistake: Not cutting the first half (forgetting
slow.next = null). Without the cut, the merge step creates a cycle — nodes from the first half still point forward into the reversed second half.