Save the pointer
before you break the link.
You already know what a linked list is. This is about the failure mode that ends interviews: losing a node because you relinked before you saved. Every sub-pattern here is one more application of the same one rule.
One rule that explains every linked-list bug
Almost every linked-list mistake in an interview collapses to a single violation: changing a node's next pointer before saving what that pointer currently holds. Once you overwrite curr.next, the node it was pointing to becomes unreachable — you've severed the only reference to it, and the rest of the list is gone.
This is not a subtle algorithmic insight. It is a mechanical discipline. The algorithms themselves (reversal, cycle detection, sub-list manipulation) are conceptually simple. The bugs are not conceptual — they are pointer-ordering bugs that happen in the three lines surrounding every relink operation.
Before changing any node's next pointer, save a reference to whatever you'll need afterward. State this out loud before you write every relink line in an interview. The rule applies to every pattern in this topic — reversal, deletion, insertion, partial reordering — without exception.
The three pointers you reach for in virtually every linked-list algorithm are a direct consequence of this rule:
prevThe node behind curr — needed to relink backward (reversal) or to splice out curr (deletion). Without it, you lose the ability to connect the chain around a removed node or point backward.currThe node currently being processed. Its next pointer is the one you are about to change — which means you must save curr.next before touching it.next_tempThe saved copy of curr.next, captured before any relinking. This is the node you'll move curr to after the relink. Without it, you have no path forward once you overwrite curr.next.The canonical order of operations within one reversal step — save, relink, advance — is not arbitrary. Each step is forced by the constraint that no reference can be overwritten before it's been saved. Every pattern in this topic uses a version of this three-step discipline.
The fast/slow pointer technique covered in the Arrays/Two-Pointers topic uses two indices moving forward through a flat array — one as a write boundary, one as a read scanner. That is fundamentally different from the fast/slow technique in this topic. Here, fast and slow are actual node references chasing each other through a pointer chain with no random access. The name is the same; the mechanism and problems are distinct. Keep this separation clear.
The dummy head node: earn it once, use it everywhere
A dummy (sentinel) head node is a fake node allocated before the real list begins, never returned as part of the answer, whose sole purpose is to eliminate special cases at the front of the list. It costs one extra allocation. It pays back by collapsing "the node to delete is the head" and "the node to delete is in the middle" into the same code path.
Without a dummy head: deletion has two branches
Suppose you want to delete the first node whose value equals val:
function delete_val(head, val): # Special case 1: empty list if head is null: return null # Special case 2: the head itself is the target if head.val == val: return head.next # General case: scan with prev/curr prev = head curr = head.next while curr is not null: if curr.val == val: prev.next = curr.next # splice out curr return head prev = curr curr = curr.next return head
With a dummy head: one code path
function delete_val(head, val): dummy = Node(0) # dummy.next will be the real head dummy.next = head prev = dummy curr = head while curr is not null: if curr.val == val: prev.next = curr.next # same line whether curr is head or not return dummy.next prev = curr curr = curr.next return dummy.next # handle no-match case
The dummy node acts as a permanent prev for whatever node is currently at the front. When curr is the real head, prev = dummy, and prev.next = curr.next correctly re-seats dummy.next to skip past the deleted node. The code is the same whether deleting the first node or the hundredth.
Whenever your logic needs to "attach something before the list" or "delete/modify the node that might be the head." In merge-two-sorted-lists, the dummy is where the merged result builds. In remove-Nth-from-end with a gap pointer, the dummy eliminates the head-deletion case. Default to using one — the cost is one allocation, the payoff is a cleaner invariant that's impossible to accidentally break at the boundary.
- Building a new list by appending nodes one at a time — dummy holds the start before any real node exists.
- Merging two lists — dummy is where both candidate nodes compete for the first slot.
- Deletion with an unknown target position — the target might be the head, which normally forces a special case.
- Any "return the new head" problem where the head itself might change — dummy.next is always the answer.
In-place reversal, pointer by pointer
Whole-list reversal is the canonical linked-list problem and the one that most directly tests the "save before relink" discipline. It also recurs as a building block inside harder problems — reversing the second half of a list before interleaving, or reversing a sub-segment as part of a k-group reordering. Get the mechanics exact here and the harder problems are just compositions of this one.
The algorithm uses exactly three pointers: prev (trailing), curr (current), and next_temp (saved forward reference). Within each iteration, the order of operations is forced:
# Step ① — ALWAYS FIRST: save forward reference next_temp = curr.next # if we skip this, ② destroys our path # Step ② — relink current node backward curr.next = prev # safe now because ① already saved forward # Step ③ — advance prev (trailing marker) prev = curr # prev now marks the head of reversed portion # Step ④ — advance curr (using saved reference, not curr.next) curr = next_temp # curr.next is now pointing BACKWARD — we use next_temp
The bug candidates make under pressure: doing ② before ① (the canonical bug — overwriting curr.next before saving it, immediately losing the rest of the list), or advancing curr using curr.next after step ② (curr.next now points backward, so this advances backward into already-reversed territory).
If you write curr.next = prev before next_temp = curr.next, the reference to the forward portion of the list is gone — permanently. You cannot recover it. The only way this bug doesn't bite immediately is if the test case is a list of length ≤ 1. Step through the widget below and notice: the next_temp pointer is the only thread connecting you to the unprocessed part of the list after each relink.
Widget A — step through the reversal, one micro-operation at a time
Each click of Step executes exactly one of the four micro-operations. Watch curr (teal), prev (amber), and next_temp (blue outline) move. The arrows between nodes flip direction as the relink step executes — that is the moment the pointer-chain changes.
Fast / slow pointer mechanics
Without an index, you can't jump to the middle of a linked list in O(1). The fast/slow pointer technique compensates: by moving two pointers at different speeds through the chain, you derive positional information from relative travel distance rather than from index arithmetic.
Three distinct problems use this mechanic in three distinct ways:
In the arrays/two-pointer topic, "fast/slow" names the read/write boundary pattern (slow = write pointer marking the finalized region; fast = read scanner). Here, fast and slow are node references chasing through a chain of pointers. The same name covers two different mechanisms. In arrays, you compact in place. In lists, you exploit relative travel distance or lap dynamics inside a cycle. Don't conflate them.
Finding the middle: when does fast stop?
For an odd-length list (n=5), fast reaches the last node (null-next) precisely when slow is at position 2 (0-indexed), the true middle. For an even-length list (n=6), the standard convention is to stop fast when fast.next == null (fast at the second-to-last node), leaving slow at the first of the two middle nodes. This matters for "reverse second half" problems — you need to know which middle convention your code uses before you start cutting the list.
Cycle detection: Floyd's algorithm, proven
The classic framing: fast moves 2 steps per iteration, slow moves 1. If a cycle exists, they eventually land on the same node. If no cycle, fast reaches null. This is correct — but candidates who have only memorized this description can rarely answer "why can't the fast pointer skip over the slow pointer inside the cycle?" Let's fix that.
Why they must meet (relative speed argument)
Once both pointers enter the cycle, think about their relative position. Let the cycle have length C. In each step, slow advances 1 node and fast advances 2 nodes, so fast gains exactly 1 node on slow per step. Starting from some relative gap G between them (0 < G ≤ C), fast closes that gap by 1 each step. When the gap reaches 0 (mod C), they are on the same node — meeting is guaranteed. The relative-gain-of-1-per-step argument also explains why fast cannot skip over slow: you can only skip if the gain per step exceeds 1, and it's exactly 1 here.
Formally: once inside the cycle, if slow is at position s and fast is at position f (both measured along the cycle), define gap = (f − s) mod C. Each step: gap → (gap + 1) mod C. Since gap increments by 1 each step and C is finite, gap must reach 0 in at most C steps. At gap = 0, f ≡ s (mod C) — same node. Skipping requires gap to jump from some positive value directly past 0 to another positive value, which requires a gain >1 per step. The gain here is exactly 1. QED.
Phase 2: finding the cycle's entry point
After detection (pointers meet at some node M inside the cycle), reset one pointer to the head while leaving the other at M. Advance both by 1 step at a time. They will meet again at the cycle's entry node E.
Why? Let D = distance from head to cycle entry E, and K = distance from E to meeting point M along the cycle. At the detection meeting point, slow has traveled D + K steps (entered cycle, traveled K steps). Fast traveled 2(D + K) steps = D + K + n·C for some integer n. So n·C = D + K, meaning D = n·C − K. Starting from head and M respectively and advancing by 1: when the head-pointer reaches E (travels D steps), the M-pointer has traveled D = n·C − K steps forward from M, which wraps around n times and lands exactly at E. They meet at the entry node.
Widget B — step through cycle detection and entry-finding
List: 1 → 2 → 3 → 4 → 5 → 6 → (back to 3). Cycle entry is node 3. Use the segment buttons to switch between Phase 1 (detection) and Phase 2 (entry finding). The red arc shows the back-edge that creates the cycle.
Sub-list reversal and k-group reversal
Full-list reversal is the base case. The real test of whether you understand the mechanics — not just the pattern — is whether you can bound the reversal to a segment [m, n] without losing the connections to the nodes before m and after n.
Reverse between positions m and n
The difficulty relative to full-list reversal: you now have four boundary pointers to track, not just two. Before starting the reversal, locate and save:
pre_mThe node before position m. After reversal, pre_m.next must point to what was node n (the new head of the reversed segment). Without a dummy head, pre_m doesn't exist when m=1 — so use a dummy.node_mThe node at position m. After reversal, this node is the new tail of the reversed segment. node_m.next must point to the node after position n (the rest of the list).node_nThe node at position n. After reversal, this is the new head of the reversed segment. Connect pre_m to it.post_nThe node after position n. After reversal, node_m.next must point here to rejoin the tail of the list.The reversal itself is identical to the full-list algorithm, just run for n − m steps starting at node_m. Before starting: pre_m.next = node_m (will be updated). After finishing: pre_m.next = node_n (new segment head), node_m.next = post_n (reconnect tail). The "save before relink" rule applies identically inside the loop.
Reverse in groups of k
A further generalization: reverse every consecutive group of k nodes. The algorithm is recursive or iterative application of the sub-list reversal, with two additional responsibilities: checking whether enough nodes remain for a full group (if the problem requires the last incomplete group to remain unchanged), and correctly threading the next pointer from the tail of one reversed group to the head of the next. The boundary pointer discipline is identical — what changes is the loop structure around it.
In full-list reversal, prev starts as null and the final prev is the new head — nothing to reattach. In sub-list reversal, you have two additional reattach operations: pre_m.next = [new head of segment] and [old head of segment, now tail].next = post_n. These two lines, and knowing which node to assign them to, are the difference between a correct sub-list reversal and a subtle corruption.
Merging and reordering
Merge two sorted lists
The merge is the simplest list-construction problem: at each step, compare the heads of two lists and append the smaller one to the result. A dummy head eliminates the "what is the first node?" question — you just append to tail (initially dummy) and the result is dummy.next.
The pointer discipline here is lighter than reversal — you're not relinking existing nodes, you're moving a tail pointer forward and changing which list's head is "next" to process. The only mandatory discipline: after the smaller node is taken, advance that list's head pointer so the same node isn't taken twice.
Merge K sorted lists
The naive approach: merge list 1 with list 2, then merge the result with list 3, and so on. This is O(N·K) where N is the total number of nodes — the first list gets touched in every merge. This topic can produce this solution; the optimal O(N log K) solution using a min-heap to always extract the globally smallest head is covered in the Heaps/Priority Queue topic. Bridge explicitly noted: if you see a "merge K sorted" problem in an interview, the question "what data structure lets me find the minimum among K candidates in O(log K)?" is the unlock, and the heap topic is where that lives.
Reorder list (composite problem)
Classic composite problem: given 1→2→3→4→5, reorder to 1→5→2→4→3 (interleave with the reversed second half). This problem requires exactly three sub-skills from this topic in sequence:
The beauty of this problem as a practice target: if you've internalized the mechanics of fast/slow and reversal, the composite almost writes itself. If you haven't, each transition between steps will produce a boundary bug. It's a reliable signal of whether the sub-skills are actually fluent.
Doubly linked lists
A doubly linked list adds a prev pointer to each node, allowing O(1) traversal in both directions and O(1) deletion given a reference to the node (because you can reach both neighbors directly). Singly linked list deletion given only the target node reference is O(n) — you need to traverse to find prev.
In interviews, doubly linked lists appear primarily as the backing structure for cache designs (LRU, LFU) rather than as a standalone topic. The reason: an LRU cache needs to move recently accessed nodes to the front in O(1), and to evict the least-recently-used node from the tail in O(1). A doubly linked list makes both O(1) given a node reference; a singly linked list makes the "move to front from an arbitrary position" case O(n).
The pointer discipline for doubly-linked operations is more involved (each relink requires updating both next and prev on multiple nodes), but the same rule applies: before changing any pointer, save what it currently points to if you'll need it after the change. The number of saves doubles; the principle doesn't change.
Singly linked list mechanics dominate interview frequency. Doubly linked lists appear most in system-design-adjacent problems (LRU Cache, Design Twitter feed) where the list is part of a larger data structure. Understand the O(1)-deletion-with-reference property and know why a singly linked list can't match it — that's the doubly-linked-list knowledge actually tested.
Rust ownership and linked lists: where the model creates real friction
In Python, Java, or C++ with shared pointers, a linked list node holds a reference (raw pointer or garbage-collected handle) to the next node. Multiple parts of your code can hold references into the same node simultaneously — a traversal pointer here, a saved reference there, two different list heads pointing into the same suffix. The language allows this without any ceremony.
Rust's ownership model does not allow this casually. A node in a naively-written Rust list owns its successor: Box<Node>. Ownership is exclusive — only one thing can own a given node at a time. This means:
prev, curr, and next_temp. In an ownership model, if curr "owns" its next node, you cannot have both a curr reference and a separate next_temp reference to the same node — only one owner is permitted. The borrow checker rejects the naive pointer-triple approach.slow and fast through a Box-based list is rejected at compile time.Rc<RefCell<T>>Shared ownership at runtime. Rc allows multiple owners (reference counting); RefCell allows interior mutability (mutable access via runtime borrow checking instead of compile-time). This is the Rust idiom for graphs and cyclic structures, and it moves the borrow-checking enforcement from compile time to runtime — you can panic at runtime for the same violation the compiler would have caught statically.Rust is not "broken" for linked lists. It is surfacing, at compile time, an aliasing concern that Python and Java let you ignore until it causes a memory bug at runtime. Multiple pointers into the same mutable structure can produce data races in concurrent code, use-after-free in systems code, and iterator-invalidation in C++. Rust rejects these statically. The friction you feel writing a linked list in Rust is the compiler telling you that the structure is inherently aliased and mutation-heavy — and that is true. A singly-linked, append-only list owned from one end is the shape Rust handles gracefully; a freely-mutable, cyclic, or multiply-referenced list is where Rc<RefCell<...>> friction actually lives.
Widget C — ownership model comparison
Left: the conventional multi-reference mental model (multiple arrows freely pointing into the same node). Right: the Rust ownership view (single owner per node, shared references explicitly annotated).
The blockchain connection: lists by hash rather than pointer
A blockchain-style ledger is, structurally, a singly linked list traversed backward by hash reference instead of by memory pointer: each block "points to" its predecessor via a cryptographic hash of that predecessor's contents rather than a raw pointer, and the chain is only valid if every link's stored hash actually matches the real contents of the block it claims to follow — conceptually the exact same "each node references the previous/next node" structure as a classic linked list, with the reference mechanism swapped from a memory address to a content hash, which incidentally makes the link tamper-evident in a way a raw pointer never could be. Altering any block changes its hash, which invalidates the stored reference in every subsequent block, making tampering structurally detectable without any central authority.
The Rust ownership discussion above maps cleanly onto this structure: building a hash-chained ledger in Rust is a case where the ownership model is a natural fit. A block owns its successor (append-only, one writer at a time, no cycles, no multiple-owner aliasing) — this is exactly the shape Box<T> handles gracefully without needing Rc<RefCell<...>>. The friction from the cycle-detection and reversal examples simply doesn't appear in an append-only chain, because the aliasing that caused the friction (multiple mutable references into the same structure, cycles) isn't present in the design.
The contrast is instructive: the ownership friction you'd face trying to implement Floyd's cycle detection natively in Rust (Box-based list, two mutable references, no Rc) reflects a real tension between the algorithm's aliasing requirements and the ownership model. That same tension is absent in the ledger, because its invariants (no mutation of existing blocks, no cycles, single-direction traversal) happen to align exactly with what Rust's ownership model handles for free.
Problem set — 10
Ordered easy → hard, spanning all sub-patterns. Four problems are flagged with the widget they directly exercise. Tap any card to expand.
Pseudocode templates
Each template matches the exact pointer order described in the prose. Cross-reference with Widget A and Widget B for the visual correspondence.
1. Full list reversal
function reverse(head): prev = null curr = head while curr is not null: next_temp = curr.next # ① save FIRST — always curr.next = prev # ② relink backward prev = curr # ③ advance prev curr = next_temp # ④ advance curr via saved ref return prev # prev is the new head
2. Floyd's cycle detection + entry point
function detect_cycle(head): slow = head fast = head # Phase 1: detect meeting point while fast is not null and fast.next is not null: slow = slow.next fast = fast.next.next if slow == fast: # cycle detected break else: return null # no cycle (fast hit null) # Phase 2: find cycle entry node ptr1 = head ptr2 = slow # ptr2 stays at meeting point while ptr1 != ptr2: ptr1 = ptr1.next ptr2 = ptr2.next return ptr1 # entry node
3. Merge two sorted lists with dummy head
function merge(l1, l2): dummy = Node(0) tail = dummy while l1 is not null and l2 is not null: if l1.val <= l2.val: tail.next = l1 # take from l1 l1 = l1.next # advance l1 head else: tail.next = l2 l2 = l2.next tail = tail.next # advance result tail tail.next = l1 if l1 else l2 # attach remaining return dummy.next
4. Reverse sub-list between positions m and n
function reverse_between(head, m, n): dummy = Node(0) dummy.next = head pre_m = dummy # Advance pre_m to node just before position m for i in 1..m-1: pre_m = pre_m.next curr = pre_m.next # node at position m (will become tail) prev = null # Reverse exactly (n - m + 1) nodes for i in 0..n-m: next_temp = curr.next # ① save curr.next = prev # ② relink prev = curr # ③ advance prev curr = next_temp # ④ advance curr # Reattach: pre_m → [new head = prev] → ... → [old head = node_m] → curr pre_m.next.next = curr # node_m (old head, now tail) → post-segment pre_m.next = prev # pre_m → node_n (new head of segment) return dummy.next
Further reading
prev tracking, what is curr tracking, and what have I saved in next_temp before I touch any pointer?" If you can't answer all three in one sentence, stop — you don't yet have a clear enough model to write correct code. Widget A is the drill: run it until you can predict each step before you click it.