Pattern 5: Combining the patterns
The "hard" linked list problems rarely bring a new idea — they fit together the patterns you already master. This lesson shows how to compose middle + reversal + merge to solve something that, at first glance, looks scary.
Try it first: Reorder List
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
Reorder the list L0 → L1 → ... → Ln-1 → Ln into L0 → Ln → L1 → Ln-1 → L2 → ... (interleaving from the start and the end), in place. Return the head.
Example: 1 → 2 → 3 → 4 → 1 → 4 → 2 → 3. 1 → 2 → 3 → 4 → 5 → 1 → 5 → 2 → 4 → 3.
Did you try? Without a plan, reordering
L0 → Ln → L1 → Ln-1 → ...in place looks chaotic. The theory below shows it is just three familiar pieces in sequence.
The theory: break it into known sub-problems
Reorder List asks you to turn L0 → L1 → ... → Ln into
L0 → Ln → L1 → Ln-1 → ... — interleaving the first half with the reversed
second half. Instead of attacking it all at once, decompose it:
- Find the middle of the list → slow/fast pattern (lesson 4).
- Reverse the second half → in-place reversal pattern (lesson 3).
- Interleave the two halves, alternating one node from each → pointer stitching (as in merge, lesson 5).
Each piece is O(n) and O(1), done one after another — so the whole thing is O(n) time and O(1) space. The "hard" one became three "easy" ones in sequence.
1 → 2 → 3 → 4 → 5
(1) middle: first [1,2,3] | second [4,5]
(2) reverse 2nd: first [1,2,3] | second [5,4]
(3) interleave: 1 → 5 → 2 → 4 → 3
The general strategy: decompose
When a list problem seems too big, ask: what familiar pieces make it up? Several "hard" ones come apart like this:
| Problem | Pieces it combines |
|---|---|
| Reorder List | middle + reversal + interleave |
| Palindrome Linked List | middle + reversal (of the 2nd half) + comparison |
| Sort List (merge sort) | middle (divide) + merge + recursion |
| Reverse Nodes in k-Group | reversal (in blocks of k) + counting |
Notice: none of them requires a brand-new idea. What separates whoever gets stuck from whoever solves it is having the patterns automated and seeing the decomposition. That is why we invested so much in each piece in the previous lessons.
🧠 Quick-check quiz
0/41. What is the central strategy for 'hard' linked list problems?
2. In Reorder List, why do slow.next = None after finding the middle?
3. Why is Reorder List O(n) time and O(1) space?
4. 'Check whether a list is a palindrome in O(1) space' decomposes into which patterns?
Summary
- Hard list problems = combinations of the basic patterns, not new ideas.
- Reorder List = middle (slow/fast) + reverse the 2nd half + interleave; each piece O(n)/O(1), so the whole thing is O(n)/O(1).
- The key skill is to decompose: "what familiar pieces make this up?".
Last stop: the section synthesis and the quiz before the final exam.