Capstone: The Linked List Final Exam
Twenty-seven posts is a lot of reading, and reading is not the same as knowing. This closing post is the check: not "did you follow along?" but "did it stick?" — can you now write the core routines cold, reproduce the complexity table from memory, and recall the handful of one-line facts that decide a whiteboard round? Work through the checklist honestly, reproduce the tables on a blank page, then take the two exams at the bottom. Anything you fumble points you back at exactly one post to reread.
The From-Memory Implementation Checklist
These are the things you should be able to write with no reference, correctly, on the first try. The times are targets for a confident candidate at a whiteboard — not a stopwatch to fear, but a signal: if a row takes you three times as long, that is the post to revisit.
| You should be able to write… | Target | From |
|---|---|---|
| A singly linked list with the rule of five (dtor, copy, move) | 8 min | singly list |
| Dummy-head insert and delete with no special head case | 4 min | sentinels |
| Pointer-to-pointer removal (delete the head with no branch) | 4 min | traversal |
| Iterative reversal (three-pointer loop) | 3 min | reversal |
| Recursive reversal, and stating its O(n) stack cost | 4 min | reversal |
| Reverse between positions m and n in one pass | 6 min | k-group |
| Reverse in k-groups, remainder left intact | 8 min | k-group |
| Find the middle, both midpoint conventions | 3 min | fast & slow |
| n-th node from the end, single pass | 4 min | fast & slow |
| Floyd cycle detection and the entrance | 6 min | cycle detection |
| Merge two sorted lists with a dummy tail | 4 min | merging |
| Merge k sorted lists (heap or divide and conquer) | 8 min | merging |
| Bottom-up merge sort in O(1) extra space | 10 min | sorting |
| Partition around a value, terminating the tail | 5 min | partitioning |
| Reorder L0→Ln→L1→Ln-1… | 7 min | reordering |
| Rotate right by k (with k reduced mod length) | 5 min | rotation |
| Palindrome check in O(1) extra space | 6 min | recursion |
| Clone a list with random pointers by weaving | 8 min | clone |
| An LRU cache: hash map + doubly linked list | 10 min | LRU cache |
| Skip-list search across levels | 8 min | skip list |
Intrusive container_of from a member pointer | 6 min | intrusive |
Rapid Recall
Step the card. It shows an operation; press again to reveal the optimal approach and its complexity. Cover the screen and answer before you flip — that retrieval effort is what moves it into long-term memory.
▶ Operation → Approach → Complexity
Ten canonical operations as flashcards. Step reveals the back of the current card, then advances to the next. It cycles, so you can drill it as long as you like.
The Complexity Table to Reproduce Cold
Write this from memory on a blank page. If any row surprises you, that operation is not yet automatic. The gotcha column is the detail interviewers probe once you state the headline numbers.
| Operation | Time | Extra space | The gotcha |
|---|---|---|---|
| Reverse entire list | O(n) | O(1) | Recursive form is O(n) stack, not O(1). |
| Find middle | O(n) | O(1) | The loop condition decides first vs second middle. |
| Detect cycle + entrance | O(n) | O(1) | Reset one pointer to head after the meet. |
| n-th node from the end | O(n) | O(1) | Anchor on a dummy so removing the head is free. |
| Merge two sorted | O(n + m) | O(1) | Attach the non-empty remainder at the end. |
| Merge k sorted | O(N log k) | O(k) | Folding one at a time is O(kN) — avoid it. |
| Sort a list (merge sort) | O(n log n) | O(1) | Bottom-up is O(1) space; top-down costs O(log n) stack. |
| Partition around x | O(n) | O(1) | Terminate the second sublist or you build a cycle. |
| Reorder L0→Ln→L1… | O(n) | O(1) | Three moves: middle, reverse tail, interleave. |
| Rotate right by k | O(n) | O(1) | Reduce k mod length before cutting. |
| Palindrome check | O(n) | O(1) | Restore the reversed half if asked to preserve input. |
| Clone with random pointers | O(n) | O(1) | Interleave clones, wire randoms, then unweave. |
| LRU cache get / put | O(1) | O(capacity) | Needs a doubly linked list; singly cannot unlink in O(1). |
Ten One-Line Facts That Decide a Round
Each of these has ended (or saved) a whiteboard answer. Commit them to memory verbatim.
- You cannot unlink a node from a singly linked list in O(1) without its predecessor — unless you cheat by copying the next node's value in and deleting that.
splicebetweenstd::lists is O(1), butstd::list::size()is O(1) only since C++11; older code walked the list to count.- Merge sort is the list sort: O(n log n), sequential access only, and O(1) extra space in the bottom-up form.
- Reversal is O(1) space iteratively but O(n) stack recursively — the recursive one overflows on long lists.
- In Floyd's algorithm, the head-to-entrance distance equals the meeting-point-to-entrance distance, which is why resetting one pointer to the head works.
- A dummy head removes the "delete the first node" special case from every deletion routine.
- Fast/slow with
while (fast && fast->next)lands the slow pointer on the second of two middles for even lengths. - An accidental cycle from a missing null-terminate hangs, it does not crash, and no memory sanitizer catches it — only a Floyd check does.
- An LRU cache needs a doubly linked list; a singly linked list cannot unlink an arbitrary used node in O(1).
- Copying an owning list with the compiler-generated copy constructor double-frees — obey the Rule of Three/Five.
Final Exam, Part A — Modules 1–2
Fundamentals, complexity, and pointer surgery. Seven questions; aim for all seven before you look anything up.
Final Exam, Part B — Modules 3–4
Advanced structures, caches, concurrency, and memory safety. Six questions.
Where to Go Next
Linked lists are the on-ramp to every pointer-based structure. The natural continuations in this collection:
- Trees & Traversals — the next recursive, pointer-linked structure; a list is a tree with one child.
- Heaps — the priority queue that makes merge-k O(N log k).
- Two Pointers on Arrays — the array cousin of fast/slow, without the cache misses.
- Graph Cycle Detection — Floyd generalises; here it becomes DFS colouring and union-find.
- Time & Space Complexity — the Big-O foundations under every claim in this series.
- Bit Manipulation — the XOR arithmetic behind the XOR linked list.
Practice
The final drill is not more reading — it is production under mild pressure. Do these and you are done.
- Reproduce the complexity table above on a blank page, then the 21-row checklist from memory. recall circle every row you could not write cold and reread that one post.
- Re-derive reversal, merge, and Floyd from scratch with autocomplete off. cold then do them again next week.
- LeetCode 146 — LRU Cache design build it end to end without notes; it is the most common design ask.
- LeetCode 25 — Reverse Nodes in k-Group hard the reconnection bookkeeping is the whole test.
- LeetCode 23 — Merge k Sorted Lists merge state both the heap and divide-and-conquer complexities.
- Return to the series overview and tick off every post whose central routine you can now write from memory. close that checklist is your real completion certificate.