Day 28 — Revision: Linked List week
revision day · linked lists · blank file, no hints
Tonight's goal: prove the linked-list pointer moves can come back from memory under pressure.
Tonight's protocol
Use the revision-day protocol: only a blank-file pass on run one or two counts.
- 0:00-0:05: scan the menu, answer the warm-up MCQs, and pick your 3 weakest problems.
- 0:05-0:30: Problem 1. Say the invariant, brute force, and target complexity out loud; code from a blank file with no hints.
- 0:30-0:55: Problem 2. Same rule: no notes, no stored code, no video, no editor history.
- 0:55-1:20: Problem 3. Stop after run two; a later pass does not count as revision done.
- 1:20-1:30: for every miss, write
WA: <root cause> and add that problem to the next revision queue.
The problem menu
Pick your 3 weakest from this menu. Re-solve each from a blank file, no hints.
Warm-up MCQs
1. Which safety rule belongs to Reverse Linked List?
“Reversal is re-aiming one arrow per step; save next before you break the link so you don't lose the rest.”
2. Which invariant removes the head special case?
“A fake head node means the real first node is never a special case, so the loop body handles every node the same way.”
3. Spot the bug in this cycle loop:
while fast:
slow = slow.next
fast = fast.next.next
“Move one pointer twice as fast; inside a cycle the gap shrinks by one each step, so they must eventually meet.”
4. Which plan finds a node measured from the end?
“Lead one pointer n steps ahead, then walk both together; when the leader hits the end, the trailer sits at the target.”
5. Which invariant matches Reorder List?
“Hard problems are compositions: find the middle, reverse the second half, then merge the two halves alternately.”
6. Which trade belongs to Copy List with Random Pointer?
“A hashmap from old node to new node lets you wire up arbitrary pointers in a second pass after all clones exist.”
Self-check gate
| Pass tonight | All 3 chosen problems pass on run one or two, and you can state the chosen invariants without looking. |
|---|
| Fail path | If any problem needs a hint, fails after run two, or has a pointer mistake, log WA: <root cause> and add it to the next revision. |
|---|
Final check: reverse 1 -> 2 -> 3 on paper with prev, curr, and nxt. If one arrow is lost, Reverse Linked List goes back into the queue.