Linked List

11 questions. The section where almost every bug is the same bug: you overwrote a pointer before saving what it pointed at.

The one idea

A linked list has no indices, no length, and no way to go backwards. All you ever hold is a handful of pointers into a structure that you are also rewiring. So:

Before you overwrite a pointer, save what it pointed at. Your only reference to the rest of the structure is the pointer you are about to destroy.

Every question here is that discipline plus one technique.

The four techniques

1. Pointer reversal — flip every next, carrying prev, cur and a saved next. (Q1, and reused inside Q3 and Q11)

2. The dummy head — allocate a throwaway node in front of the list so that "append the first node" and "remove the head" stop being special cases. (Q2, Q4, Q6, Q9, Q10, Q11 — six of eleven)

The dummy head removes the empty-list special case

3. Two pointers — in two flavours, and it's worth keeping them distinct:

Fixed gap — open a gap of n and slide both. When the leader hits the end, the trailer is n from it. (Q4)
Different speeds — fast moves two, slow moves one. Used to find the middle (Q3) and to detect cycles (Q7, Q8).

4. Compose two structures — when one structure can't give you both properties you need, wire two together. (Q9)

Easy Reverse Linked List LC 206 11 min Easy Merge Two Sorted Lists LC 21 10 min Medium Reorder List LC 143 10 min Medium Remove Nth Node From End of List LC 19 10 min Medium Copy List With Random Pointer LC 138 11 min Medium Add Two Numbers LC 2 11 min Easy Linked List Cycle LC 141 11 min Medium Find the Duplicate Number LC 287 12 min Medium LRU Cache LC 146 14 min Hard Merge K Sorted Lists LC 23 13 min Hard Reverse Nodes in K-Group LC 25 13 min

Floyd's cycle detection — the one to actually understand

Two pointers, one moving twice as fast. If there's a cycle they must meet, because the gap between them shrinks by exactly 1 each step and a quantity decreasing by exactly 1 cannot skip zero.

Finding where the cycle starts needs one more step, and one piece of algebra:

Why resetting to the head finds the entrance

slow walked a + b; fast walked twice that. If fast lapped once, it walked a + b + (b + c). So 2(a+b) = a + 2b + c, giving a = c — the head-to-entrance distance equals the meeting-point-to-entrance distance.

This is what makes question 8 possible, where there is no list at all — just an array whose values happen to be valid indices.

The null-check that appears everywhere

Java

while (fast != null && fast.next != null)

Both clauses, in that order. fast.next.next dereferences twice, so you must establish both before hopping — and && short-circuits, so swapping the operands throws on a null head.

The traps

Trap	Symptom
Overwriting `cur.next` before saving it	The rest of the list is unreachable
`prev = cur` before `cur.next = prev`	Self-loop; infinite list
Forgetting `slow.next = null` when splitting (Q3)	Halves stay joined; weave never terminates
`while (fast != null)` instead of `fast.next != null` (Q4)	`slow` lands one node too far
Dropping the final carry (Q6)	`99 + 1` returns 0, not 100
Comparing `slow.val == fast.val` (Q7)	Duplicate values look like a cycle
Singly linked list in an LRU (Q9)	Unlink becomes `O(n)`; the design collapses
Merging k lists one at a time (Q10)	`O(N·k)` — the accumulator is re-walked
Reversing before checking k nodes remain (Q11)	A partial tail gets reversed and can't be cheaply undone

Verification

Every Java snippet in this section was compiled and cross-checked against an independent implementation — 5,000+ randomized cases, including:

three reversal implementations agreeing on 500 random lists
Q5 verified structurally: the copy shares no node with the original, every random lands on the correct copy, and the input is left byte-for-byte intact
Q6 checked against BigInteger on 600 random pairs
Q9 checked against LinkedHashMap in access-order mode over 400 traces of 60 operations
Q11 checked against an independent array-chunk reversal

Two deliberately-broken variants confirm the guards are load-bearing rather than decorative:

dropping carry != 0 from Q6's loop condition returns [0,0] for 99 + 1 instead of [0,0,1]
not moving the node on get in Q9 turns LRU into FIFO — it disagreed on 1,055 lookups