Linked List Patterns
Linked list questions are pointer discipline exercises. There is very little algorithmic depth, and that is precisely why they are asked: the code either handles the empty list, the single node and the final node correctly, or it does not. Nearly everything reduces to three ideas, which are a pair of pointers moving at different speeds, an in-place reversal, and a dummy node that removes the special case at the head.
Where to start, and what comes next
- 01
Fast & Slow Pointers
Cycle detection and finding the middle. Both are short, and they establish the two-pointer habit the rest of the topic relies on.
- 02
In-Place Reversal
The three-pointer reversal, which is the single most reused piece of code here. Sublist and k-group reversal are variations on it.
- 03
Merge & Sort
Merging sorted lists and sorting a list. This is where the dummy node earns its place and where merge sort turns out to suit lists better than arrays.
- 04
Design Problems
LRU cache and copying a list with random pointers. Both combine a list with a hash map, which is the pattern behind most real uses.
If you only have time for three things
- The three-pointer reversal, and remembering to return prev rather than curr, which is null by the time the loop ends.
- A dummy node before the head, which removes every special case around modifying the first element.
- Fast and slow pointers, including the second phase that finds the cycle entrance after they meet.
Draw the pointers. Almost every mistake in this topic comes from overwriting a next pointer before saving it, and a sketch catches that immediately where mental simulation does not. Interviewers also tend to probe the edge cases directly, so say up front what happens on an empty list and a single node rather than waiting to be asked.
The idea underneath
Most linked list problems are about pointer manipulation. Draw it out! Fast & slow pointers detect cycles and find midpoints. In-place reversal is the other core technique.
Problems that use these patterns
Head to head
Questions people ask
Why does resetting to the head find the cycle entrance?
It falls out of the arithmetic. If the tail before the cycle has length a and the pointers met b nodes into the cycle, the fast pointer has travelled exactly twice the slow one, which forces a to equal the remaining distance from the meeting point back to the entrance. So two pointers moving at equal speed from the head and the meeting point converge there.
When is a dummy node worth it?
Whenever the head itself might be removed or replaced. Without one, every such case needs a separate branch, and that branch is where the bugs are. It costs one allocation and removes a class of error.
Why merge sort rather than quicksort for a linked list?
Quicksort's partition wants random access, which a list does not have, so each level costs a full traversal. Merge sort only ever moves forward, which is exactly what a list supports, and it needs no extra array because the merge just rewires pointers.