Linked List
Overview
Linked lists aren’t dominant in production code anymore, dynamic arrays have better cache behavior, but they remain the workhorse of pointer-manipulation interviews. Mastering them means internalizing five patterns:
- Reversal (iterative and recursive): the building block under everything else.
- Two-pointer slow/fast: middle, cycle detection, n-from-end.
- Dummy head node: simplifies edge cases at the head.
- Merging: pointer splicing of sorted sequences.
- Composite structures: hash map + doubly linked list (LRU cache).
Problems
- 206. Reverse Linked List (Easy)
- 21. Merge Two Sorted Lists (Easy)
- 141. Linked List Cycle (Easy)
- 160. Intersection of Two Linked Lists (Easy)
- 876. Middle of the Linked List (Easy)
- 143. Reorder List (Medium)
- 19. Remove Nth Node From End of List (Medium)
- 24. Swap Nodes in Pairs (Medium)
- 138. Copy List with Random Pointer (Medium)
- 2. Add Two Numbers (Medium)
- 287. Find the Duplicate Number (Medium)
- 146. LRU Cache (Medium)
- 23. Merge k Sorted Lists (Hard)
- 25. Reverse Nodes in k-Group (Hard)
Key patterns unlocked here
- Three-pointer reversal: 206 (iterative and recursive).
- Two-pointer merge: 21.
- Floyd’s tortoise and hare: 141 (linked list), 287 (array-as-linked-list).
- Find middle + reverse + interleave: 143.
- Offset-n two pointers: 19.
- Interwoven-copy technique for auxiliary pointers: 138.
- Digit-by-digit addition with carry: 2.
- Hash map + doubly linked list (LRU cache template): 146.
- Divide-and-conquer merge or min-heap of heads: 23.
- Reverse-in-segments with bookkeeping: 25.