Linked List
Dummy nodes, fast and slow pointers, merging and rewiring.
4 notes · 22 min total
Questions0 of 26 done
Warm up with these before Phase 1.
Patterns
- 1Dummy Node & Pointer RewiringPut a dummy node before the head so deleting, inserting and swapping work the same everywhere, and rewire pointers in a safe order.6 min
- 2Fast/Slow & Gap PointersUse two pointers at different speeds or a fixed distance apart to find cycles, cycle entries, middles and the k-th node from the end.7 min
- 3Merging & Sorting ListsMerge sorted lists by splicing nodes onto a dummy tail, and sort a list in O(n log n) with merge sort split by fast/slow pointers.4 min
- 4Hashing & Prefix Sums on ListsUse hash maps and sets on linked lists: prefix sums to cut zero-sum runs, membership checks for components, and node maps for copies.5 min