What must survive reversal?

A(4)→B(4)→C(9) are three existing objects.

Would allocating [9,4,4] satisfy a request to reverse these nodes?

After changing A.Next, what still reaches B?

1 / 12

Linked List Cycle — predict before coding

Pointer identity describes topology; equal values do not create a cycle. Two speeds exploit a deterministic next-pointer graph without allocating a visited set.

Decision: Can an acyclic list whose node values are [7,7,7] be declared cyclic by value equality?

Presenter notes

Model answer: No. Distinct nodes may share the same value. Only revisiting or meeting the same pointer establishes a cycle.

Correctness argument: If the list is acyclic, the fast pointer eventually reaches nil or a node whose next is nil, so the guarded loop returns false. If a cycle exists, both pointers eventually enter it. Thereafter their relative position changes by one edge per iteration modulo the cycle length because fast moves two edges and slow one. Within at most one cycle length their relative offset becomes zero, so they meet at the same node and return true. The equality test occurs after movement, avoiding the trivial initial equality at head. No next pointers are changed.

Debugging prompt: Include nil, a self-loop, a cycle entering at head, and a long non-cyclic prefix. Check fast and fast.Next before dereferencing two steps.

2 / 12

Linked List Cycle II — predict before coding

The first meeting locates a point in the cycle, not necessarily its entrance. A second equal-speed phase uses the modular distance accumulated by Floyd's traversal.

Decision: For a list 0→1→2→3→4→2, which node must be returned, even if the first meeting is elsewhere?

Presenter notes

Model answer: The exact node at position 2. Its value alone is not enough to identify the answer, and the first Floyd meeting need not be that node.

Correctness argument: Let a be the distance from head to the cycle entry, c the cycle length, and t the slow pointer's steps at a meeting. The fast pointer has traveled 2t, so their difference t is a multiple of c. The meeting point's offset from entry is (t-a) modulo c, meaning it is a steps modulo c before the entry. Reset one pointer to head and advance both one edge at a time. After a steps the reset pointer reaches the entry and the meeting pointer also reaches it. Before that, the reset pointer is outside the cycle, so they cannot meet earlier. If the first phase reaches nil, no entry exists.

Debugging prompt: Test cycles of length one after a nonempty prefix and cycles starting at head. Return the original entry pointer, never a newly allocated node with an equal value.

3 / 12

Add Two Numbers — predict before coding

Reverse digit order makes ordinary column addition streamable. The carry is the only information that must pass from one digit position to the next.

Decision: What reverse-order digit list results from [9,9] plus [1]?

Presenter notes

Model answer: [0,0,1], representing 99+1=100. The last node comes from carry after both inputs are exhausted.

Correctness argument: Before processing digit position i, the output contains the correct low i digits of the sum and carry is the amount owed to position i. Read each available input digit, treating an exhausted list as zero, and add them with carry. Division by ten produces the next carry and remainder modulo ten produces exactly the current decimal digit. Appending a new node preserves the arithmetic invariant and leaves the inputs untouched. Continue while either input or carry remains; otherwise a final carry would be lost. When all three are exhausted, no higher contribution remains, so the output represents the full sum.

Debugging prompt: Test unequal lengths, cascading carry, zero, and input preservation. Do not convert a 100000-digit list to a machine integer. The reference allocates a fresh result list.

4 / 12

Merge Two Sorted Lists — predict before coding

The next smallest remaining value must be one of the two heads. Splicing existing nodes avoids allocating a second list while a dummy head removes the first-node special case.

Decision: When the two current heads both hold 2, does selecting either invalidate sortedness?

Presenter notes

Model answer: No. Both are minimum remaining values. The supplied reference chooses the first list on equality; its ordering remains stable within each input list.

Correctness argument: The built prefix is sorted and contains exactly the nodes already removed from the two input prefixes; tail identifies its last node. Since each remainder is sorted, the smaller current head is no greater than any other remaining node. Linking that node after tail therefore extends the correct sorted prefix and consumes it once. When one remainder is empty, the other is already sorted and no smaller than the built prefix, so it can be attached wholesale. Every original node is included exactly once and no result-data node is allocated. The returned dummy.Next is the first real node.

Debugging prompt: Test nil on either side, equal values, and alternating small values. Verify result node identities and termination, not only the value sequence; accidental cycles can otherwise hide behind a bounded printout.

5 / 12

Copy List with Random Pointer — predict before coding

Deep copying requires preserving relationships, not just values. A map from original identity to clone identity lets forward and backward random links be connected after all clones exist.

Decision: If two original nodes point Random to the same third node, should the clone contain one or two copies of that target?

Presenter notes

Model answer: One clone of the target, shared by both cloned Random pointers. Allocating separately per edge would change the graph topology.

Correctness argument: In the first pass, allocate exactly one clone for every node in the finite next chain and record the original-to-clone map. The map is injective because each original receives a fresh allocation. In the second pass, assign each clone's Next and Random to the mapped copies of the original targets; nil maps to nil. Every original edge is thereby reproduced between clone identities, including self-random edges, backward links, and several nodes sharing one random target. No clone points into the original list, and no original edge or value is modified. Thus the result is a graph-isomorphic deep copy.

Debugging prompt: Use duplicate node values, self-random links, nil random links, and shared random targets. Build the original-to-clone correspondence by position and assert pointer disjointness and unchanged original edges.

6 / 12

Reverse Linked List — predict before coding

Reversal consumes the original forward chain while constructing a backward chain. Saving the next pointer is what prevents a destructive write from losing the unread suffix.

Decision: Why must next be saved before assigning cur.Next=prev?

Presenter notes

Model answer: After the assignment, cur.Next no longer identifies the original successor. Without the saved pointer, the remaining suffix becomes unreachable from the local traversal.

Correctness argument: Before each iteration, prev heads the reversed processed prefix and cur heads the untouched original suffix; together they contain all original nodes exactly once. Save cur.Next before changing it. Redirecting cur.Next to prev moves exactly the first suffix node onto the reversed prefix. Advancing prev to cur and cur to the saved next restores the invariant with one fewer unread node. The new edge points only into the processed prefix, so it cannot create a cycle with the untouched suffix. When cur is nil, prev heads all nodes in reverse order and is the required new head.

Debugging prompt: Assert exact pointer order, not just reversed values. Include equal-valued nodes so a value-swapping implementation cannot masquerade as node reversal.

7 / 12

Reverse Linked List II — predict before coding

An anchor before the segment lets repeated head insertion reverse only the selected region. The original first segment node becomes its stable tail.

Decision: For 1→2→3→4→5 with left=2 and right=4, which node becomes the tail of the reversed segment?

Presenter notes

Model answer: The original node 2. The final chain is 1→4→3→2→5; cur stays at node 2 during repeated front insertion.

Correctness argument: Move prev to the node immediately before the one-based left position, using a dummy when left=1. Let cur remain the original first node of the segment. After k insertions, the first k+1 selected nodes appear in reversed order after prev, cur is their tail, and the unprocessed suffix still follows cur. Detach cur.Next and insert it immediately after prev; this extends the reversed selected prefix by one without touching nodes outside the segment. Repeating right-left times reverses exactly the requested positions. The saved anchor and stable tail reconnect the unchanged prefix and suffix automatically.

Debugging prompt: Test left=1, right=length, and left=right. Positions are one-based and valid: 1<=left<=right<=list length. Verify original node reuse and no cycles.

8 / 12

Reverse Nodes in k-Group — predict before coding

Checking group size before rewiring is essential: an incomplete final group is not a smaller reversal problem, because its original order must be preserved.

Decision: What does reversing groups of 3 do to 1→2→3→4→5?

Presenter notes

Model answer: 3→2→1→4→5. The final two-node group is incomplete and must remain 4→5, not become 5→4.

Correctness argument: At each group boundary, the processed prefix already consists of correctly reversed full groups and groupPrev is its final node. Look ahead k nodes without modification. If fewer exist, the untouched suffix must remain in original order and the algorithm terminates. Otherwise save the node after the group and reverse exactly the k links, initializing the reversed-chain tail connection to that saved successor. Connect groupPrev to the group's new head and advance groupPrev to its original first node, now its tail. This extends the invariant by one complete group. Each node participates in at most one lookahead and one reversal.

Debugging prompt: Test k=1, k larger than length, exact multiples, and one node short of a full final group. Check pointer identity to distinguish node reversal from value reassignment.

9 / 12

Remove Nth Node From End of List — predict before coding

A fixed pointer gap turns an end-relative rank into a predecessor location. The dummy head makes removing the actual head an ordinary link update.

Decision: For a three-node list, which node is removed when n=3, and why is a dummy useful?

Presenter notes

Model answer: The original head is removed. Slow stays at the dummy, so updating slow.Next handles this case without a separate head-removal branch.

Correctness argument: Start slow and fast at a dummy node and advance fast n edges. Their separation is now n edges. Move both while fast.Next exists; each simultaneous step preserves the gap. At termination fast is the final real node, so slow is immediately before the node with n nodes from itself through the end. Bypassing slow.Next removes exactly the nth node from the end. If n equals the original length, slow remains the dummy and the same assignment replaces the head. Every other node retains its relative order and identity.

Debugging prompt: Use a singleton, removal of the tail, and removal of the head. The contract guarantees 1<=n<=length; do not hide an off-by-one by adding arbitrary invalid-input behavior.

10 / 12

LRU Cache — predict before coding

The map answers where a key lives; the doubly linked list answers which key is oldest. Neither structure alone provides both constant-time lookup and recency updates.

Decision: At capacity 2, after Put(1,10), Put(2,20), Get(1), Put(3,30), which key is evicted?

Presenter notes

Model answer: Key 2. Get(1) refreshed key 1, so key 2 was least recently used when key 3 arrived.

Correctness argument: Maintain a one-to-one correspondence between map entries and real list nodes, with the list ordered from most recently used at the front to least recently used at the back. A successful Get returns the mapped value and moves that node to the most-recent end, preserving membership while updating the required order. Put on an existing key changes its value and moves the same node, without increasing size. Put on a new key inserts one mapped node; if capacity is exceeded, remove the least-recent real node from both the list and map. Dummy endpoints make every splice uniform. Each operation therefore preserves the capacity, value, membership, and recency invariants.

Debugging prompt: Use a simple map plus recency slice as an independent model. Exercise updates of existing keys, repeated gets, misses, capacity one, and independent cache instances.

11 / 12

An access-ordered playlist

A playlist must find a song by ID, move a played song to the front, and discard the oldest when full.

Why does a hash map plus a singly linked list still leave an O(n) operation? Derive the missing state.

12 / 12