Synthesis: which pattern to use?
Five linked list patterns covered. Time to train the reflex: read a prompt and know which tool (or combination) to pull out — with justification.
The section's decision tree
1. Can the operation touch the HEAD (remove/insert at the start, merge)?
→ use a DUMMY NODE to avoid special cases
2. Do I need something "N nodes from the end" or the MIDDLE of the list?
├── "n-th from the end" → TWO POINTERS with a fixed gap of n
└── "middle of the list" → SLOW/FAST (fast +2, slow +1)
3. Is the question about a CYCLE (the list closes on itself)?
→ FLOYD (slow/fast): if the hare catches the tortoise, there is a cycle
4. Do I need to REVERSE the order (the whole list or a stretch)?
→ IN-PLACE REVERSAL (three pointers: prev, curr, next)
5. Merging two SORTED lists?
→ MERGE with a dummy (stitch the smaller head each time)
6. Does it look hard / do several things?
→ DECOMPOSE into the pieces above (middle + reversal + merge...)
And the reflexes that hold for the whole section: save curr.next before
overwriting it (or you lose the rest), and use a dummy whenever the head
might change.
The full map of the section
| Pattern | Key question | Time | Space |
|---|---|---|---|
| Dummy node | "does the operation touch the head?" | O(n) | O(1) |
| Two pointers (gap) | "n-th from the end" | O(n) | O(1) |
| Slow/fast | "middle of the list" | O(n) | O(1) |
| Floyd | "is there a cycle?" | O(n) | O(1) |
| In-place reversal | "reverse the order" | O(n) | O(1) |
| Merge | "merge two sorted lists" | O(n+m) | O(1) |
Notice the space column: all O(1). That is the signature of the section — linked lists reward whoever manipulates pointers instead of copying into arrays. When one of your solutions uses O(n) memory, ask whether it can be done by just relinking.
Section quiz
Prompts you have not seen in the lessons. Identify the pattern (or the combination) and why. 7+ correct: you are ready for the exam.
🧠 Section quiz: Linked List
0/81. 'Check whether a linked list is a palindrome, using O(1) space.' Which combination?
2. 'Find the node where two lists intersect.' Which tool from the section helps?
3. 'Remove all nodes with a specific value, even if it is the head.' Why use a dummy?
4. 'Detect whether there is a cycle and, if so, return the node where it begins.' Which pattern is the basis?
5. 'Add two numbers represented by linked lists (one digit per node).' Which tool avoids handling the head separately?
6. 'Sort a linked list in O(n log n) and O(1) extra space.' Which patterns make up merge sort on a list?
7. What is the parent idea that unites the WHOLE linked list section?
8. Which implementation mistake is the most common in reversing/reordering lists?
Ready for the exam?
The final exam for the Linked List section has three new problems — easy, medium, and hard — with hidden test cases. The hard one (reverse in groups of k) combines in-place reversal with group counting: exactly the kind of decomposition from the previous lesson. The five lessons cover everything you need.
Good luck! Go back to the section page and click "Final exam".