RE-ROUTING THE ARROWS
YOUR CALL
The hard linked-list problems are not new techniques — they are deck 2's tricks composed. Merging is the engine of sort-list and merge-k; reversing a sublist is reverse-in-k-group; a dummy and a ring give you rotate; the clone-with-random-pointer has one beautiful O(1) trick; and the LRU cache is a doubly list married to a hash map. Learn how the pieces fit and the “hard” tag stops meaning difficult and starts meaning assembled.
This is not a list of problems. It is 7 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
ASSUMEDA min-heap (priority queue) in unit 02 — push, pop-min, O(log k). Heaps is step 11 and not built yet, so the unit explains what it needs.
7 PROBLEMS · EVERY ONE LINKS TO LEETCODE TO SOLVE
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the sheet's row, not your position — the deck teaches in the order that builds, so you will meet them slightly out of numerical sequence.
Seven hards, and not one new idea — each is deck 2's tricks assembled. The cards below name the composition a statement is asking for.
the two-way merge of sorted lists is the engine; a heap generalises it to k
MERGE (dummy + pick smaller); MIN-HEAP for kO(n log n) sort · O(N log k) for kthe 3-pointer reversal applied to a window, with boundary bookkeeping
SUBLIST REVERSAL + reconnectO(n) time · O(1) spaceclose the list into a ring, walk to the new break, cut
RING + CUT (find length, k %= n)O(n) time · O(1) spaceinterleave each clone beside its original so random is one hop away
INTERLEAVE-CLONE-SPLIT (or a hash map)O(n) time · O(1) spacea hash map for lookup, a doubly linked list for recency order
MAP + DOUBLY LIST (move-to-front, evict-tail)O(1) per operationit is almost always two easy pieces — a merge, a reversal, a dummy — composed
DECOMPOSE into the deck-2 tricksrecognise, then assembleThe hards are about picking the right structure, not raw n. A heap turns merge-k from quadratic to log; a map beside a list makes the LRU O(1). The gold rows are the winning choices.
COMPLEXITY COMES FROM THE STRUCTURE, NOT THE SIZE · HEAP · MERGE-SORT · MAP+LIST
Seven set-pieces: the merge family (three), a windowed reversal, a ring rotate, the clone-interleave, and the LRU. Each leans on a deck-2 trick — this deck is about assembly.
Merging k sorted lists by merging them in one at a time is O(N·k). What makes the heap approach O(N log k)?
You only ever choose among k candidates. The next node of the answer is the minimum of the k list-heads, so a min-heap of those heads delivers it in O(log k); pop it, push its successor, repeat. Over all N nodes that is O(N log k). Merging one list in at a time re-scans the growing result, doing O(N·k) work. Same answer, but the heap keeps the comparison set tiny — that is the entire optimisation.
Why is merge sort the natural choice for sorting a linked list, where quicksort is the usual array default?
Lists give merge sort everything and quicksort nothing. Merge sort splits by walking to the middle (fast/slow) and combines by re-linking nodes — no random access, no extra array, stable, guaranteed O(n log n). Quicksort relies on O(1) indexing to pick and partition around a pivot, which a linked list cannot provide, so it degrades. This is why “sort a linked list” is really “merge sort a linked list.”
The LRU cache needs O(1) get and put. Why does it take BOTH a hash map and a doubly linked list — why not one structure?
Neither structure alone is O(1) for both jobs. A hash map finds a node by key instantly but has no notion of recency order; a doubly linked list maintains recency (move a node to the front, drop the tail) in O(1) but cannot find a key without scanning. Together, the map's value is a pointer into the list, so get locates the node via the map and splices it to the front, and put evicts the tail when full — every step O(1). It is the canonical “two structures, complementary weaknesses” design.
Merging two sorted lists is the engine under sort-list and merge-k, so it earns its own unit. Keep a dummy head and a tail; at each step compare the two fronts, attach the smaller to tail, and advance that list. When one list empties, the other is already sorted — attach its whole remaining tail in O(1). No new nodes, just re-linking.
HOW DO YOU MERGE TWO SORTED LISTS INTO ONE, WITHOUT COPYING NODES?
Once one of the two lists is exhausted, what do you do with the other?
Attach the whole leftover tail at once. The remaining list is already sorted and every one of its values is ≥ the last one you placed, so you simply set tail->next to its head — a single pointer assignment, O(1). Continuing to loop and compare against nothing wastes time and invites null-pointer slips. This “attach the rest” move is why the merge is linear and clean.
Why does this merge routine reappear in both sort-list and merge-k-lists?
It is the reusable combine step. Merge sort splits then merges two sorted halves — this routine. Merge-k either runs log k rounds of pairwise merges (this routine, repeatedly) or uses a heap that is the same “pick the smallest front” idea across k lists. Master the two-way merge and the whole merge family becomes bookkeeping around it.
Merging two sorted lists is the engine under half of deck 3. Keep a dummy and a tail; at each step compare the two fronts, attach the smaller, and advance that list. When one runs out, the other is already sorted — attach its whole tail in O(1) rather than copying. No new nodes: you are re-linking the existing ones. Return dummy.next.
“Merge two sorted lists into one sorted list.” The base case of the whole merge family — a dummy head and a two-pointer walk.
Dummy head, tail pointer. While both lists have nodes, attach the smaller front to tail and advance that list. When one empties, attach the other's remaining tail whole. Return dummy.next.
// Dummy head + pick the smaller front; attach the leftover tail whole. ListNode* mergeTwoLists(ListNode* a, ListNode* b) { ListNode dummy(0); ListNode* tail = &dummy; while (a && b) { if (a->val <= b->val) { tail->next = a; a = a->next; } else { tail->next = b; b = b->next; } tail = tail->next; } tail->next = a ? a : b; // one is empty; attach the rest return dummy.next; }
// Dummy head + pick the smaller front; attach the leftover tail whole. public ListNode mergeTwoLists(ListNode a, ListNode b) { ListNode dummy = new ListNode(0); ListNode tail = dummy; while (a != null && b != null) { if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; } tail = tail.next; } tail.next = (a != null) ? a : b; // one is empty; attach the rest return dummy.next; }
# Dummy head + pick the smaller front; attach the leftover tail whole. def mergeTwoLists(a, b): dummy = ListNode(0) tail = dummy while a and b: if a.val <= b.val: tail.next = a; a = a.next else: tail.next = b; b = b.next tail = tail.next tail.next = a if a else b # attach the rest return dummy.next
Looping past the end, or copying nodes. Once either list is empty, attach the other's whole tail in one assignment — continuing to compare risks a null dereference. And you re-link the existing nodes; allocating new ones is wasteful. Use <= (not <) to keep the merge stable.
The walkthrough for #01 Merge Two Sorted Lists. Watch it, then go straight back and write it yourself.
The smallest un-placed element is always one of the k current list-heads, so keep those heads in a min-heap: pop the smallest, append it, and push that node's successor. Each of the N nodes enters and leaves the heap once at O(log k), so the whole merge is O(N log k) — the right complexity, versus O(N·k) for merging one list in at a time.
HOW DO YOU MERGE k SORTED LISTS WITHOUT RE-SCANNING A GROWING RESULT?
After popping the minimum head from the heap and appending it, what do you push back?
Push the popped node's next. The heap's invariant is “one entry per list, its current head.” When you remove a list's head as the global minimum, that list's new head is node->next, so you push it (if non-null) to keep the invariant. The heap size stays ≤ k, which is what pins each operation at O(log k) and the total at O(N log k).
Merge-k can also be done by divide-and-conquer. What is that approach, and its complexity?
Pairwise merging over log k rounds. Merge lists 1&2, 3&4, …; that halves the number of lists and touches all N nodes once (O(N)). Repeat, and after log k rounds a single sorted list remains — total O(N log k), the same as the heap. It reuses the two-way merge directly, so if unit 1 is solid this is nearly free. Two routes, one bound: recognising both is the mark of really owning merge-k.
The smallest remaining element is always one of the k current heads, so keep them in a min-heap: pop the smallest, append it, and push that node's successor. Each of the N nodes is pushed and popped once at O(log k), giving O(N log k) — far better than merging one list in at a time (O(Nk)). The divide-and-conquer alternative, merging lists pairwise over log k rounds, hits the same bound.
“Merge k sorted lists into one.” The next output is always the minimum of the k current heads — a min-heap, or divide-and-conquer pairwise merging.
Push each list's head into a min-heap keyed by value. Repeatedly pop the smallest, append it to a dummy-headed result, and push that node's next. The heap stays size ≤ k, so each of N nodes costs O(log k).
// A min-heap of the k heads: pop the smallest, push its successor. ListNode* mergeKLists(vector<ListNode*>& lists) { auto cmp = [](ListNode* a, ListNode* b){ return a->val > b->val; }; priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp); for (ListNode* l : lists) if (l) pq.push(l); ListNode dummy(0), *tail = &dummy; while (!pq.empty()) { ListNode* node = pq.top(); pq.pop(); tail->next = node; tail = node; if (node->next) pq.push(node->next); } return dummy.next; }
// A min-heap of the k heads: pop the smallest, push its successor. public ListNode mergeKLists(ListNode[] lists) { PriorityQueue<ListNode> pq = new PriorityQueue<>((x, y) -> Integer.compare(x.val, y.val)); for (ListNode l : lists) if (l != null) pq.add(l); ListNode dummy = new ListNode(0), tail = dummy; while (!pq.isEmpty()) { ListNode node = pq.poll(); tail.next = node; tail = node; if (node.next != null) pq.add(node.next); } return dummy.next; }
# A min-heap of the k heads: pop the smallest, push its successor. import heapq def mergeKLists(lists): heap = [] for i, l in enumerate(lists): if l: heapq.heappush(heap, (l.val, i, l)) # i breaks val ties dummy = ListNode(0); tail = dummy while heap: _, i, node = heapq.heappop(heap) tail.next = node; tail = node if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) return dummy.next
Merging one list in at a time (O(N·k)), or an unstable heap comparator. Feeding lists into an accumulator re-walks the growing result; the heap keeps the comparison set at k. In Python, push a tie-breaker (the list index) so the heap never tries to compare two ListNodes directly. Divide-and-conquer pairwise merging is an equally good O(N log k) alternative.
The walkthrough for #02 Merge k Sorted Lists. Watch it, then go straight back and write it yourself.
Sorting a linked list in O(n log n) is merge sort, and a list suits it perfectly: split at the middle with fast/slow, sort each half recursively, then merge the two with the unit-1 routine. No auxiliary array — the combine step just re-links nodes — and unlike quicksort it needs no random access for a pivot.
HOW DO YOU SORT A LINKED LIST IN O(n log n) WITHOUT AN ARRAY?
This merge sort recurses forever on a 2-node list. What did the split forget?
ListNode* mid = findMiddle(head); ListNode* left = sortList(head); // mid was found, but head's half was never cut ListNode* right = sortList(mid);
You must cut the list into two independent halves. findMiddle gives you mid, but unless you sever the link before it (prevOfMid->next = nullptr), the “left” half still points straight through mid into the rest, so sortList(head) re-sorts everything and the subproblem never gets smaller — infinite recursion. The split is two steps: find the middle, and terminate the first half.
Why merge sort rather than quicksort for a linked list?
The list's access pattern fits merge sort and starves quicksort. Merge sort only ever walks forward and re-links nodes, so it needs no auxiliary array and stays a clean O(n log n); splitting is a fast/slow walk and merging is unit 1. Quicksort's speed comes from O(1) indexing to choose a good pivot and partition in place — precisely what a linked list cannot do — so it degrades badly. “Sort a list” means merge sort.
Sorting a linked list in O(n log n) is merge sort, and lists suit it perfectly: split at the middle with fast/slow, sort each half recursively, then merge the two with the unit-1 routine. Quicksort is a poor fit (no random access for a good pivot), and merge sort needs no auxiliary array here — the combine step just re-links nodes. It is the clearest example of the deck's thesis: a hard problem is two easy ones stacked.
“Sort a linked list”, ideally O(n log n) and O(1) space. That is merge sort on a list: split, sort, merge.
Find the middle with fast/slow and cut the list into two halves there. Recursively sort each half, then merge them with the unit-1 routine. Top-down is O(log n) stack; bottom-up is truly O(1) space.
// Merge sort: split at the middle, sort each half, merge (unit 1). ListNode* sortList(ListNode* head) { if (!head || !head->next) return head; ListNode *slow = head, *fast = head->next; // find & cut the middle while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } ListNode* mid = slow->next; slow->next = nullptr; // CUT the first half ListNode* left = sortList(head); ListNode* right = sortList(mid); return mergeTwoLists(left, right); // combine }
// Merge sort: split at the middle, sort each half, merge (unit 1). public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; ListNode slow = head, fast = head.next; // find & cut the middle while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode mid = slow.next; slow.next = null; // CUT the first half ListNode left = sortList(head); ListNode right = sortList(mid); return mergeTwoLists(left, right); // combine }
# Merge sort: split at the middle, sort each half, merge (unit 1). def sortList(head): if not head or not head.next: return head slow, fast = head, head.next # find & cut the middle while fast and fast.next: slow, fast = slow.next, fast.next.next mid = slow.next slow.next = None # CUT the first half left = sortList(head) right = sortList(mid) return mergeTwoLists(left, right) # combine
Not cutting the first half. After finding mid you must set the node-before-mid's next to null, or the two halves still share nodes and the recursion never shrinks — a stack overflow. Starting fast at head->next makes slow land on the last node of the first half, which is exactly where you cut.
The walkthrough for #03 Sort List. Watch it, then go straight back and write it yourself.
Reverse-nodes-in-k-group is the unit-2 three-pointer reversal applied to a window of k at a time. Before reversing a block, confirm it has k nodes (walk k ahead); a trailing block shorter than k is left untouched. After reversing, reconnect: the previous block's tail links to this block's new head, and this block's new tail links onward.
HOW DO YOU REVERSE THE LIST IN FIXED BLOCKS, LEAVING A SHORT TAIL ALONE?
Before reversing a group of k nodes, what must you verify, and why?
Confirm k nodes remain before touching the block. The problem specifies that a final group smaller than k keeps its original order, so you walk k nodes ahead first; if you fall off the end, return that block unchanged. Reversing an incomplete block (or reversing before checking) is the standard wrong answer. Once the block is known to have k nodes, reverse it with the unit-2 dance and stitch the boundaries.
What is the extra work in reverse-in-k-group beyond a plain reversal?
Boundary bookkeeping between blocks. The reversal itself is unit 2 verbatim; the difficulty is threading the reversed chunks together. After reversing a block, its old head is now the tail and must connect to whatever comes next (the next reversed block, or the leftover), and the previous block must point to this block's new head. Track those two boundary nodes carefully and the “hard” problem is just reversal with plumbing.
Reverse-in-k-group is the unit-2 reversal applied to a window of k. Before touching a block, check it actually has k nodes (walk k ahead); if not, leave it as-is. Reverse the block with prev/curr/next, then reconnect: the previous block's tail points to this block's new head, and this block's new tail (the old head) links onward. The bookkeeping of the boundary nodes is the only thing beyond a plain reversal.
“Reverse the nodes in groups of k”, leaving a trailing block shorter than k as-is. The unit-2 reversal applied to a window, plus boundary reconnection.
Check the next k nodes exist; if not, return the block unchanged. Otherwise reverse those k nodes with prev/curr/next, then recurse on the rest and link the old head to whatever the recursion returns. The old head becomes the block's tail; the last node reversed becomes its head.
// Verify k nodes, reverse the block, recurse, reconnect boundaries. ListNode* reverseKGroup(ListNode* head, int k) { ListNode* node = head; for (int i = 0; i < k; i++) { // enough nodes for a full block? if (!node) return head; // fewer than k: keep as-is node = node->next; } ListNode* prev = reverseKGroup(node, k); // 'node' is the (k+1)-th; recurse ListNode* curr = head; for (int i = 0; i < k; i++) { // reverse this block, linking ListNode* next = curr->next; // to the already-reversed rest curr->next = prev; prev = curr; curr = next; } return prev; // new head of this block }
// Verify k nodes, reverse the block, recurse, reconnect boundaries. public ListNode reverseKGroup(ListNode head, int k) { ListNode node = head; for (int i = 0; i < k; i++) { // enough nodes for a full block? if (node == null) return head; // fewer than k: keep as-is node = node.next; } ListNode prev = reverseKGroup(node, k); // 'node' is the (k+1)-th; recurse ListNode curr = head; for (int i = 0; i < k; i++) { // reverse this block, linking ListNode next = curr.next; // to the already-reversed rest curr.next = prev; prev = curr; curr = next; } return prev; // new head of this block }
# Verify k nodes, reverse the block, recurse, reconnect boundaries. def reverseKGroup(head, k): node = head for _ in range(k): # enough nodes for a full block? if not node: return head # fewer than k: keep as-is node = node.next prev = reverseKGroup(node, k) # recurse on the rest first curr = head for _ in range(k): # reverse this block onto 'prev' nxt = curr.next curr.next = prev; prev = curr; curr = nxt return prev # new head of this block
Reversing before checking the block is full. Walk k nodes ahead first; a trailing group shorter than k must stay in order. The other difficulty is reconnection — each reversed block's old head becomes its tail and must link to the next block's new head, which the recursive form handles by reversing “onto” the already-processed remainder.
The walkthrough for #04 Reverse Nodes in k-Group. Watch it, then go straight back and write it yourself.
Rotating right by k is pure restructuring: two link changes move a block from the back to the front. Find the length n, take k %= n (rotations wrap), then join the tail to the head to make a ring. The new head sits k nodes before the old tail — at index n − k — so walk to the node just before it and cut the ring.
HOW DO YOU MOVE THE LAST k NODES TO THE FRONT WITH JUST TWO LINK CHANGES?
Why compute k %= n before rotating?
Rotations are cyclic, so only k mod n matters. If k ≥ n, walking k steps overshoots; and rotating by exactly n (or 2n, …) lands back where you started. Taking k %= n collapses all of that to the effective shift, so you walk to index n − k once. Skipping the modulo is the most common rotate bug — it passes small samples and fails when k is large.
Rotate 1 → 2 → 3 → 4 → 5 right by k = 2. What is the result, and where is the new head?
4 → 5 → 1 → 2 → 3. Rotating right by 2 moves the last two nodes (4, 5) to the front. With n = 5, the new head is at index n − k = 3 (value 4), and the new tail is index 2 (value 3). Close the ring, walk to node 3, cut after it. The MECHANISM slide shows the tail-to-head back-edge forming, then the cut at the new spot.
Rotating right by k is pure restructuring. Find the length n, take k %= n (rotations wrap), then join the tail to the head to form a ring. The new head is k nodes before the old tail — i.e. at index n − k — so walk to the node just before it (the new tail) and cut the ring there. Two link changes move an arbitrary block from the back to the front.
“Rotate the list right by k.” Restructuring: find the length, close into a ring, and cut at the new head position.
Find the length n and the tail. Take k %= n. Join tail->next = head to form a ring. Walk n − k − 1 steps from the head to the new tail; the node after it is the new head. Cut newTail->next = null.
// Close into a ring, walk to index n-k-1, cut there. ListNode* rotateRight(ListNode* head, int k) { if (!head || !head->next || k == 0) return head; int n = 1; ListNode* tail = head; while (tail->next) { tail = tail->next; n++; } // length + tail k %= n; if (k == 0) return head; tail->next = head; // close the ring ListNode* newTail = head; for (int i = 0; i < n - k - 1; i++) newTail = newTail->next; ListNode* newHead = newTail->next; newTail->next = nullptr; // cut return newHead; }
// Close into a ring, walk to index n-k-1, cut there. public ListNode rotateRight(ListNode head, int k) { if (head == null || head.next == null || k == 0) return head; int n = 1; ListNode tail = head; while (tail.next != null) { tail = tail.next; n++; } // length + tail k %= n; if (k == 0) return head; tail.next = head; // close the ring ListNode newTail = head; for (int i = 0; i < n - k - 1; i++) newTail = newTail.next; ListNode newHead = newTail.next; newTail.next = null; // cut return newHead; }
# Close into a ring, walk to index n-k-1, cut there. def rotateRight(head, k): if not head or not head.next or k == 0: return head n, tail = 1, head while tail.next: # length + tail tail, n = tail.next, n + 1 k %= n if k == 0: return head tail.next = head # close the ring new_tail = head for _ in range(n - k - 1): new_tail = new_tail.next new_head = new_tail.next new_tail.next = None # cut return new_head
Forgetting k %= n. k can exceed the length, and rotating by a multiple of n is a no-op; without the modulo you walk off the ring or do needless work. Guard the empty and single-node lists, and remember the new head is at index n − k — the new tail is the node right before it.
The walkthrough for #05 Rotate List. Watch it, then go straight back and write it yourself.
Deep-copying a list whose nodes carry an extra random pointer, in O(1) space, hinges on one trick: interleave. Insert each clone right after its original (A → A′ → B → B′ → …). Now the clone of any node X is exactly X->next, so clone->random = X->random->next — no hash map. Finally unweave the two lists apart.
HOW DO YOU COPY random POINTERS WITHOUT A MAP FROM ORIGINAL TO CLONE?
After interleaving clones (A → A′ → B → B′ → …), why is a clone's random pointer simply orig->random->next?
Interleaving makes the original→clone map positional. If orig's random target is some node R, then R's clone is sitting right after R — at R->next, i.e. orig->random->next. So the clone's random pointer is available in O(1) with no dictionary. This is the whole reason to weave the clones in beside the originals rather than building a separate list.
The simpler solution uses a hash map from each original node to its clone. What is the trade-off versus interleaving?
Space versus simplicity. The hash-map approach is easy to reason about — map original→clone, then wire up next and random by lookup — but it costs O(n) extra memory. Interleaving gets to O(1) space by encoding that mapping in the list's own structure, paying with the care needed to weave clones in, set randoms, and cleanly unweave (restoring the original's next pointers). Both are O(n) time; the follow-up that matters asks for O(1) space.
Deep-copying a list with random pointers in O(1) space hinges on one idea: interleave. First insert each clone right after its original (A → A′ → B → B′ → …). Now the clone of any node X sits at X->next, so clone->random = X->random->next — no hash map needed. Finally unweave the interleaved list back into the original and the copy. Three linear passes, constant extra space.
“Deep copy a list where each node has a random pointer”, ideally O(1) space. The elegant trick is to interleave each clone beside its original.
Weave a clone after each original (A → A′ → B → B′ → …). Then each clone's random is orig->random->next, because the clone of any node sits right after it. Finally unweave the interleaved list back into the original and the copy, restoring the originals' next pointers.
// Interleave clones so clone->random = orig->random->next; then unweave. Node* copyRandomList(Node* head) { if (!head) return nullptr; for (Node* p = head; p; p = p->next->next) { // 1) weave clones in Node* c = new Node(p->val); c->next = p->next; p->next = c; } for (Node* p = head; p; p = p->next->next) // 2) set clone randoms p->next->random = p->random ? p->random->next : nullptr; Node dummy(0), *ct = &dummy; // 3) unweave for (Node* p = head; p; p = p->next) { ct->next = p->next; ct = ct->next; p->next = p->next->next; // restore original } return dummy.next; }
// Interleave clones so clone.random = orig.random.next; then unweave. public Node copyRandomList(Node head) { if (head == null) return null; for (Node p = head; p != null; p = p.next.next) { // 1) weave clones in Node c = new Node(p.val); c.next = p.next; p.next = c; } for (Node p = head; p != null; p = p.next.next) // 2) set clone randoms p.next.random = (p.random != null) ? p.random.next : null; Node dummy = new Node(0), ct = dummy; // 3) unweave for (Node p = head; p != null; p = p.next) { ct.next = p.next; ct = ct.next; p.next = p.next.next; } return dummy.next; }
# Interleave clones so clone.random = orig.random.next; then unweave. def copyRandomList(head): if not head: return None p = head # 1) weave clones in while p: c = Node(p.val) c.next = p.next; p.next = c p = c.next p = head # 2) set clone randoms while p: p.next.random = p.random.next if p.random else None p = p.next.next dummy = Node(0); ct = dummy; p = head # 3) unweave while p: ct.next = p.next; ct = ct.next p.next = p.next.next # restore original p = p.next return dummy.next
Setting randoms after splitting, or leaving the original corrupted. Wire the clones' random pointers while still interleaved — once unwoven, orig->random->next no longer points at the clone. And as you split, restore each original's next, or you return a mangled input list.
The walkthrough for #06 Copy List with Random Pointer. Watch it, then go straight back and write it yourself.
An LRU cache is two structures married so each covers the other's weakness: a hash map for O(1) lookup of a key's node, and a doubly linked list for O(1) recency ordering — move a used node to the front, evict from the tail (always the least-recently-used). get splices the node to the front; put evicts the tail when full, then inserts at the front.
HOW DO YOU GET O(1) get AND put, WITH EVICTION OF THE LEAST-RECENTLY-USED?
On a get(key) that hits, what are the two actions?
Return the value and promote the node to the front. A get counts as a use, so the node becomes the most-recently-used and must move to the head — otherwise the recency order is wrong and you would eventually evict a hot key. The map locates the node in O(1); the doubly list lets you unlink and re-insert at the front in O(1). Forgetting the move-to-front is a silent correctness bug that only shows up under the right eviction sequence.
When put must evict because the cache is full, which node goes, and what must not be forgotten?
Evict the tail, and clean the map. By construction the tail is the least-recently-used node, so it is the one to drop. The subtlety is that the hash map still holds that key pointing at the now-removed node; failing to erase it leaves a dangling entry that will later return a freed node or mis-count the size. The invariant is simple but strict: the map and the list must agree after every operation.
The LRU cache is the marriage of two structures, each covering the other's weakness. A hash map gives O(1) lookup of a key's node; a doubly linked list keeps nodes in recency order with O(1) move-to-front and evict-from-tail (the tail is always the least-recently-used). get splices the node to the front; put evicts the tail when full, then inserts at the front. Every operation is O(1) — and it is exactly why deck 1 taught the doubly list.
“Design an LRU cache with O(1) get and put.” The canonical hash-map-plus-doubly-linked-list design.
A hash map maps key → node for O(1) lookup; a doubly linked list keeps nodes in recency order (head = most recent, tail = least). get finds the node via the map and moves it to the front; put updates or inserts at the front and, if over capacity, evicts the tail and erases its key.
// Hash map (find) + doubly linked list (recency: head=MRU, tail=LRU). class LRUCache { int cap; list<pair<int,int>> dll; // {key, val}, front = MRU unordered_map<int, list<pair<int,int>>::iterator> mp; public: LRUCache(int capacity) : cap(capacity) {} int get(int key) { auto it = mp.find(key); if (it == mp.end()) return -1; dll.splice(dll.begin(), dll, it->second); // move node to front return it->second->second; } void put(int key, int value) { auto it = mp.find(key); if (it != mp.end()) dll.erase(it->second); dll.push_front({key, value}); mp[key] = dll.begin(); if ((int)dll.size() > cap) { // evict the LRU tail mp.erase(dll.back().first); dll.pop_back(); } } };
// LinkedHashMap IS the hash map plus the recency list, in one type. class LRUCache { private final int cap; private final LinkedHashMap<Integer, Integer> map; public LRUCache(int capacity) { cap = capacity; // accessOrder = true: a get() moves the entry to the MRU end map = new LinkedHashMap<>(16, 0.75f, true); } public int get(int key) { return map.getOrDefault(key, -1); // the get itself reorders } public void put(int key, int value) { map.put(key, value); if (map.size() > cap) { // evict the LRU end int oldest = map.keySet().iterator().next(); map.remove(oldest); } } }
# OrderedDict is a hash map + doubly linked list in one. from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.cap = capacity self.d = OrderedDict() def get(self, key): if key not in self.d: return -1 self.d.move_to_end(key) # mark most-recently-used return self.d[key] def put(self, key, value): if key in self.d: self.d.move_to_end(key) self.d[key] = value if len(self.d) > self.cap: self.d.popitem(last=False) # evict the least-recently-used
Stale map entries and the move-to-front. On eviction, erase the tail's key from the map — a dangling entry is the classic LRU bug. And a successful get must promote the node to the front, or recency order rots and a hot key gets evicted. The map and the list must agree after every single operation.
Sort-list, merge-k, and merge-two look like three problems. What single routine do all three depend on?
The two-way merge. Merge-two-sorted-lists is the primitive; merge sort's combine phase calls it on the two sorted halves; and merge-k is the same idea scaled to k inputs (a min-heap picks the smallest head, or you merge pairwise in log k rounds). Learn the merge once and three-quarters of the “merge” family is written. That is the compositional payoff this deck keeps pointing at.
Copy-list-with-random can be done with a hash map (original → clone) in O(n) space. What does the interleaving trick buy, and how?
O(1) space instead of O(n). The hash-map solution stores a mapping from every original node to its clone so it can wire the random pointers; the interleaving trick makes that mapping positional — the clone of X is always X->next, so clone->random = X->random->next with no map at all. Three linear passes (weave, set randoms, unweave) and constant extra memory. Recognising that “I need a map from A to B” can sometimes become “put B next to A” is the transferable idea.
The hards fail on the seams: an O(N·k) merge, an uncut split, an incomplete k-block, a forgotten modulo, a stale map entry. Every one compiles and passes the sample.
Repeatedly merging the next list into an accumulator re-walks the growing result — O(N·k). Use a min-heap of the k heads (O(N log k)) or divide-and-conquer pairwise merges (log k rounds).
When you split with fast/slow, you must cut the first half by setting the node-before-middle's next to null; forget it and the two halves still share nodes, and the recursion never terminates.
Only reverse a group once you've confirmed it has k nodes — walk k ahead first. A trailing block shorter than k stays as-is, and reconnecting the reversed block's new tail to the next group is the fiddly part.
k may be larger than the length, so take k %= n first — otherwise you walk off the ring. And rotating by a multiple of n is a no-op; the modulo handles that too.
Set every clone's random before you unweave — once separated, orig->random->next no longer points at the clone. And restore the original list's next pointers as you split, or you hand back a corrupted input.
When you evict the tail node, you must also erase its key from the hash map; leaving a dangling map entry pointing at a freed node is the classic LRU bug. Update the map on every insert, move, and evict.
Seven set-pieces, one page. The right-hand column is the assembly — the structures and moves that turn each “hard” into a couple of easy pieces.
Merge, reverse-a-window, ring-and-cut, interleave, map-plus-list — every hard was deck 2's tricks assembled. That is the whole of linked lists: a node and a pointer, a handful of moves, and the judgement to see which composition a problem is quietly asking for.
Lectures are Striver's A2Z linked-list playlist (L21–L23, L25–L27). Problems are LeetCode; LRU Cache is taught outside this playlist, so it ships without a solution video.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.