Linked List

Reader guide and study workflow · Complete course map

Start with the objects you must preserve

Draw three separately allocated nodes A(4), B(4), C(9), with A→B→C. The request is to reverse their order while keeping the same nodes. Before choosing an algorithm, decide whether building new nodes with values [9,4,4] satisfies that request. It reproduces a value sequence but changes identity: a caller holding B would still see the old node. This distinction determines which operations are legal.

A direct solution stores the three original pointers in an array and reconnects them backward. That is an honest O(n)-space baseline. Now remove the array one entry at a time. At the moment A.Next is replaced, what is the only route to B? Save B first. We have derived the state prev = reversed prefix, cur = first untouched node, and next = the successor about to lose its incoming edge. The assignment order follows from preserving reachability, not from remembering four lines.

Pause after reversing A and B: prev=B→A→nil, cur=C. There are still exactly three original nodes, split between two disjoint chains. Connecting C to prev finishes the job. This is a useful invariant because it says both what is already correct and where unfinished work remains.

Change the request before reusing the method

Reverse only A and B: now A must eventually point to C. Reverse groups of three in a five-node list: establish that three nodes exist before touching a group's links, because the incomplete suffix must survive unchanged. Remove A: its predecessor does not exist, so a temporary dummy predecessor makes the head case obey the same bypass operation as interior nodes. None of these changes permits altering Val.

A different request, adding digit lists, deliberately allocates an independent result; a clone must allocate exactly one new node for each old one. State the ownership contract before sharing a helper across these exercises.

Derive a second structure from a failed baseline

For LRU, an ordered slice of keys can model recency correctly, but a hit in its middle costs O(n) to move. A map locates the node directly; a doubly linked list provides both neighboring links so removal and front insertion need constant work. The two structures solve different missing operations and must describe exactly the same live entries. A singly linked list plus a key→node map still lacks the predecessor needed for constant-time removal.

Prerequisites and readiness

Know pointer identity versus value equality, nil, ownership of mutable links, and the difference between allocating nodes and rewiring them. Draw each changed Next edge before coding.

Reasoning workshop: preserve reachability before changing topology

Two chains during reversal

For 1→2→3, start with prev=nil and cur at node 1. Save node 2 before changing node 1's Next to nil. The state is then reversed prefix 1→nil and untouched suffix 2→3. On the next step, save node 3, point node 2 back to node 1, and advance. The state sentence explains the assignment order: after an edge is destroyed, another saved reference must still reach the unread suffix.

A dummy head is not a fake output node. It provides a stable predecessor for operations that may change the real head, such as removing the nth-from-end node or reversing a segment beginning at position 1. Return dummy.Next, not the dummy itself. For a three-node list and n=3, the removal predecessor stays at the dummy, so the head case becomes the same bypass operation as every other case.

Segment boundaries are part of the proof

ReverseBetween keeps the node before the segment fixed and repeatedly moves the next node after the original segment head to the segment front. That original head becomes the tail. ReverseKGroup must first establish that a complete group exists: with five nodes and k=3, the final two nodes remain in their original order. Reversing first and trying to undo an incomplete group adds complexity and invites reconnection errors.

Merging sorted lists consumes two node frontiers and reuses their nodes. Adding reversed-digit numbers instead allocates a new result and leaves both inputs intact. For [9,9]+[1], carry produces [0,0,1]; the carry-only final iteration is essential. A shared “linked list output” helper must not erase these different ownership contracts.

Cycle identity and entry arithmetic

Repeated values are not a cycle. Floyd compares actual pointers after movement. If a cycle exists, the relative offset of the fast and slow pointers advances by one modulo its length until they meet. The first meeting may not be the entry. If head-to-entry distance is a and the meeting occurs after t slow steps, t is a multiple of the cycle length; moving one pointer from head and one from the meeting at equal speed makes both reach the entry after a steps. This is why the reset phase works, not a coincidence to memorize.

Copy relationships, not just payloads

A random-pointer clone needs one new node per original node, even when several originals have equal values. Allocate all clones first, then translate every original Next and Random edge through the map. Two originals sharing a random target must share that target's single clone. Test disjoint identities, preserved values, reproduced edges, and unchanged original pointers.

LRU keeps two synchronized representations

The reference places most-recent nodes near the dummy head and least-recent nodes near the dummy tail. The map and real list nodes must correspond one-to-one. A Get hit moves a node; a miss does not insert one. Updating an existing key refreshes recency without increasing size. At capacity two, Put(1), Put(2), Get(1), Put(3) evicts key 2. A simple ordered-key slice makes a useful independent test model even though it is too slow for the required implementation.

Reconstruction lab and answer key

Linked List Cycle

On A→B→C→D→E→C, put slow and fast at A and advance before comparing. At which node do they first meet? Would changing every Val to 0 affect the result?

Model answer

After successive iterations the pointer pairs are (B,C), (C,E), (D,D), so the first meeting is D. Values are irrelevant: the argument follows Next edges and compares identities. The meeting proves a cycle but does not identify its entry.

Linked List Cycle II

A list enters a four-node cycle after five edges. Floyd meets after eight slow steps. How far is that meeting past the entry, and why do five equal-speed reset steps still reach the entry?

Model answer

The meeting is (8−5) mod 4 = 3 edges past the entry. Five more steps move it 8 edges from the entry, which is 0 modulo 4. The reset pointer from head also reaches the entry after five steps. The remaining cycle distance is 1, not literally 5; congruence, including full laps, is the reason.

Add Two Numbers

Work [8,9,9] plus [7,1] one column at a time. Name the output digit and carry after each column, including any column with no input node.

Model answer

The sums are 8+7=15 (digit 5, carry 1), 9+1+1=11 (digit 1, carry 1), 9+0+1=10 (digit 0, carry 1), then carry-only 1 (digit 1, carry 0). The result is [5,1,0,1], representing 998+17=1015. Reading input nodes does not transfer their ownership to the result.

Merge Two Sorted Lists

Input nodes A(1)→B(3) and C(1)→D(2) have distinct identities. Give two valid identity orders after merging. What would a test miss if it checked only [1,1,2,3]?

Model answer

A→C→D→B and C→A→D→B are both sorted and contain each original node once. Values alone would accept newly allocated replacements, duplicated/missing equal-valued nodes, or mutations that keep the output values plausible. Check identities, original payloads, and termination without imposing a cross-input tie order.

Copy List with Random Pointer

A and B both hold 5; A.Next=B, A.Random=A, and B.Random=A. Describe all copied edges and explain why a map keyed by value cannot work.

Model answer

Create distinct A′ and B′, both separate from the originals. A′.Next=B′, A′.Random=A′, B′.Next=nil, and B′.Random=A′. A value-keyed map collapses A and B into one object, losing both node count and topology. Original fields must stay unchanged.

Reverse Linked List

Two callers hold different heads that share a suffix of original node objects. A new requirement says reverse one caller’s list while the other caller must still see its original Next chain. Can ordinary in-place reversal satisfy both? Explain the contract choice.

Model answer

No in general: shared nodes have one Next field, so reversing an edge for one caller also changes what the other sees. Either require exclusive ownership before mutation or allocate a separate reversed copy and relax the same-node output requirement. Additional local pointers cannot give one object two contradictory Next values.

Reverse Linked List II

On A→B→C→D→E, reverse positions 2 through 4 using head insertion. What is the list after each move, which node stays the segment tail, and where does it point at the end?

Model answer

Move C immediately after A to obtain A→C→B→D→E. Then move D after A to obtain A→D→C→B→E. B stays the segment tail and ends at E. Save the moved node, detach it from after B, link it to the current segment front, then update A.Next.

Reverse Nodes in k-Group

For A→B→C→D→E→F→G with k=3, identify the groups, final identity order, and the lookahead that prevents corrupting the suffix.

Model answer

The complete groups are A,B,C and D,E,F; G is incomplete. Return C→B→A→F→E→D→G. Before changing a group, walk k nodes from its predecessor to establish a kth node and save the following boundary. When fewer than k remain, stop without changing their links.

Remove Nth Node From End of List

Use a dummy and an n-edge lead to remove the fourth node from the end of A→B→C→D. Where are fast and slow before the paired loop? Why are there zero paired moves?

Model answer

Starting both at dummy and advancing fast four edges puts fast at D and slow at dummy. Because fast.Next is already nil, no paired move is needed. slow.Next is A, so dummy.Next becomes B. Using fast!=nil as this version’s loop guard would advance the predecessor one node too far.

LRU Cache

Capacity is 2. Apply Put(4,40), Put(7,70), Put(4,41), Get(9), Put(8,80). Give the final order most-recent first and explain the effect of the miss and the update.

Model answer

The orders are [4], [7,4], [4,7], [4,7], then [8,4]. Updating 4 changes its value to 41 and refreshes it without increasing size. Get(9) returns -1 and leaves recency unchanged. Inserting 8 evicts 7. The map must contain exactly keys 8 and 4, matching the two real list nodes.

Problems in this module

• Linked List Cycle
• Linked List Cycle II
• Add Two Numbers
• Merge Two Sorted Lists
• Copy List with Random Pointer
• Reverse Linked List
• Reverse Linked List II
• Reverse Nodes in k-Group
• Remove Nth Node From End of List
• LRU Cache

Interactive checkpoint

Open the Linked List quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable