Topic 7 of 20
Pointer manipulation: reversal, fast & slow pointers, merging and cache design.
A linked list stores elements in nodes that point to the next node, so insertion and deletion are O(1) once you are at the right spot, but random access is O(n). Linked-list questions are really pointer-manipulation questions. They test whether you can rewire next pointers without losing part of the list, so draw the boxes and arrows before you code.
Three techniques cover most problems. A dummy head node removes special cases when the real head might change. In-place reversal (keep prev, curr and next) is used on its own and inside harder problems such as reversing in groups of k. Fast & slow pointers, where one moves two steps for every one step of the other, find the middle, detect cycles and even locate the start of a cycle (Floyd's algorithm).
The topic ends with design problems such as the LRU cache, where a hash map gives O(1) lookup and a doubly linked list gives O(1) reordering. That pairing is one of the most frequently asked design questions at every large company.
The single most important linked-list routine; do it iteratively and recursively.
Dummy head plus merge, reused in merge sort and k-way merge.
Floyd's cycle detection in its simplest form.
Fast/slow to find the midpoint, a sub-step of many problems.
Basic pointer skipping on sorted data.
Shows why a dummy head removes head-deletion special cases.
Combines finding the middle with reversing the second half.
Switching heads equalises path lengths, an elegant trick.
A fixed gap between two pointers in one pass.
Chains three core routines together; a great consolidation problem.
Digit-by-digit addition with a carry; very frequently asked.
Deep copy with arbitrary pointers; the interleaving trick gives O(1) space.
The maths behind finding a cycle's start with Floyd's algorithm.
Treating an array as a linked list to find a cycle; a famous insight.
Local pointer rewiring in pairs.
Reversal of a sub-range with correct reconnection.
Make a ring, then cut it at the right place.
Partitions nodes into two chains in place.
Removing whole runs needs a dummy head and a careful look-ahead.
Merge sort on a linked list in O(n log n).
One of the most-asked design questions at every FAANG company.
Heap-based or divide-and-conquer merging; a classic Hard.
Group-wise reversal: the hardest pure pointer problem.
An LRU follow-up with frequency buckets.
O(1) inc/dec/min/max with a bucket list.