Linked lists have no random access — every operation is pointer surgery. Master three tools and you can solve nearly the entire category: a dummy head to tame edge cases, fast & slow pointers for middle/cycle problems, and iterative reversal (prev/curr/next rewiring). The payoff is almost always O(n) time and O(1) space.
You can't jump to a position in a linked list — you can only stand on a node and follow .next. So every algorithm is just a few cursors crawling forward, rewiring arrows as they pass — and the whole craft is reassigning those arrows in the right order so you never lose the rest of the list.
An array is one slab of memory, so a[2] is a single hop. A linked list is a scavenger hunt: each node holds a value and an arrow to the next. There is no c[2] — to reach the third node you physically walk head.next.next, one arrow at a time.
array : a[0] a[1] a[2] a[3] a[2] is one hop → O(1)
└──── one block of memory ────┘
list : head → a → b → c → null
to reach c you must walk: head.next.next
there is NO c[2]. only ".next, .next, .next".
So every list algorithm = a few CURSORS walking forward,
rewiring arrows as they pass. You never index — you follow.So stop picturing positions and start picturing fingers (cursors) resting on nodes. An algorithm is: place one or two fingers, slide them forward, and occasionally re-point an arrow. That reframe — “which arrows do I move, and in what order?” — is the entire category.
.next am I about to overwrite?”Reversal is the whole game in miniature: save the forward arrow, flip it backward, then march all three cursors one node right. Watch a single step:
BEFORE a step curr.next points FORWARD (a → b)
prev curr next
│ │ │
null ◄── a b → c → null
└──────► (curr.next still = b, saved into 'next')
AFTER curr.next = prev the arrow between prev and curr is FLIPPED
prev curr next
│ │ │
null ◄── a b → c → null
└──► points back at prev (null here)
THEN march: prev = curr; curr = next (all three slide right)
... null ◄── a b c → null
│ │ │
prev curr nextAnd the two-speed trick: a fast cursor moving twice as fast as a slow one. If the list loops, fast keeps lapping the track and collides with slow — that collision is the proof of a cycle (Floyd):
slow +1 per step, fast +2. If there's a loop, fast laps slow.
1 → 2 → 3 → 4 → 5
▲ │
└─── 7 ◄┘ 6 (tail 7 points back to 4: a cycle)
t0: slow=1 fast=1
t1: slow=2 fast=3
t2: slow=3 fast=5
t3: slow=4 fast=7
t4: slow=5 fast=5 ◄── tortoise & hare MEET → cycle exists
No loop? fast walks off the end (hits null) and you stop.
Meeting node is NOT the entry — reset one cursor to head,
then step both +1; they re-meet exactly at the cycle's entry.Faced with a linked-list problem, don't reach for code. Pin down which tool first by climbing these rungs in order:
dummy.next.n finds the nth from the end..next before you overwrite it. The instant you assign curr.next = something, the old tail is gone unless you stashed it first.The highest-leverage habit in this category is a one-line mantra you say before every pointer assignment: “save .nextfirst, flip second, march third.”A linked-list cursor only knows the node it's on and the one arrow leaving it — once you overwrite that arrow, the rest of the list is unreachable. There is no going back.
next = curr.next (save), curr.next = prev (flip), prev = curr; curr = next(march).”tailalways points at the last node I've committed; splice the smaller head, then advance tail.”fast then fast.next before stepping fast.next.next.”curr.next = prev before saving next silently amputates the tail. If your reversed list comes back length-1 or your loop hangs, you almost certainly skipped the save.Strip away the problem and almost every list algorithm is one of two shapes. The reversal loop — save → flip → march → march — read as a sentence, not as code:
reverse(head):
prev = null # nothing behind us yet
curr = head
while curr is not null:
next = curr.next # 1. SAVE — or lose the rest forever
curr.next = prev # 2. FLIP — point this node backward
prev = curr # 3. MARCH prev forward
curr = next # 4. MARCH curr forward
return prev # prev is the new headAnd the cursor-placement shapes, where the only thing that changes is how you space and pace the two cursors:
# front edits (insert/delete head)? → DUMMY HEAD
dummy = node(next = head)
... operate on dummy.next ...
return dummy.next
# middle / cycle / nth-from-end? → TWO SPEEDS
slow = fast = head
while fast and fast.next: # guard: fast FIRST, then fast.next
slow = slow.next # +1
fast = fast.next.next # +2 (slow lands on the middle)
# nth-from-end? give fast an n-step head start, THEN walk together —
# the gap of n means slow stops n nodes before the end.The walking and the arrow-saving never change; what changes is how many cursors, how far apart, and how fast. Internalize these two skeletons and the category collapses into “pick the spacing.”
The front of a list is the one place that has no predecessor — so inserting before it or deleting it normally needs its own special-case branch. A dummy (sentinel) node planted before head erases that asymmetry: now the real head has a prev too, and one uniform loop handles every position.
WITHOUT dummy — deleting the head is a special case:
head → 7 → 3 → 9 → null ("if head is target: head=head.next")
WITH dummy — a fake node sits before head:
dummy → head → 7 → 3 → 9 → null
│ │
return every real node now has a "prev", even the first.
dummy.next
prev.next = prev.next.next ← works for the head too.Use it in merge two sorted lists(the result head isn't known until the first comparison), remove nth from end (the head itself might be the node removed), and add two numbers (the first digit is built the same way as the rest). At the end you always return dummy.next — never the sentinel, whose val is garbage.
prev.next = prev.next.next deletes the head exactly the way it deletes any middle node. No branch, no edge case.prev / cur / next dance: save next first (or you lose the rest of the list), point cur back at prev, then march all three forward. Step it in the Visualize tab — exactly one arrow flips per beat.An array lets you jump to index i in O(1). A linked list does not. To reach the kth node you walk from head, one .next at a time. This forces every algorithm to be written as a single forward traversal (or at most two passes).
The core skill is drawing the pointers on paper before you code. Label every node you are about to touch, write the four-step rewiring order, then transcribe it. A wrong order loses the rest of the list permanently — there is no going back.
prev, curr, and next on a three-node diagram before touching the keyboard. Every pointer bug comes from a missing or wrong-order assignment.When a problem might modify the head node (delete it, insert before it, or produce an empty result), create a sentinel:
const dummy = { val: 0, next: head };All your logic then operates on dummy.next and beyond. You never have to special-case "what if head is null" or "what if I'm deleting the first node" — the dummy absorbs it. Return dummy.next at the end.
Two pointers starting at the same node but advancing at different speeds let you answer distance-based questions in a single pass:
fast moves 2 steps, slow moves 1. When fast hits the end, slow is at the middle.fast laps slow and they meet. If no cycle, fast exits through null.head and advance both 1 step — they meet exactly at the entry node.fast !== null && fast.next !== null (in that order) before dereferencing fast.next.next. The wrong check is the most common runtime crash in this pattern.Reversing a list (or a sublist) is a four-line loop once you internalize the order:
next = curr.next before you overwrite anything.curr.next = prev.prev = curr.curr = next.When the loop ends, prev is the new head. Forgetting step 1 — saving next — loses every node after curr permanently.
prev = null, cur = head. Every arrow still points right. Flip one arrow at a time.Reach for linked-list techniques when the problem hands you a ListNode head or describes a chain where elements must be reordered, split, merged, or inspected without extra memory. The three tools above cover nearly every variant.
| "reverse a list / reverse a sublist" | iterative prev/curr/next reversal; track the four boundary pointers for a sublist |
| "find the middle of a linked list" | fast & slow: fast exits when slow is at mid |
| "detect a cycle / find cycle entry" | Floyd's fast & slow — meet inside, then reset one pointer to head |
| "remove nth node from end" | two pointers with an n-gap advance using a dummy head |
| "merge two (or k) sorted lists" | dummy head + splice-smaller loop; k lists → divide-and-conquer or min-heap |
| "reorder list / palindrome linked list" | find middle (fast/slow), reverse second half, then weave or compare |
| "deep copy with random pointers" | hash map old→new node; or interleave cloned nodes in-place then separate |
When → Any time you need to flip link directions — reverse a whole list or a sublist. The same four-line body is used as a subroutine inside harder problems (reorder list, reverse k-group).
// Shared node shape (used by all templates below)
interface ListNode {
val: number;
next: ListNode | null;
}
// Iterative reversal — O(n) time, O(1) space
// Draw on paper: prev <-- curr next (saved)
function reverseList(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null;
let curr = head;
while (curr !== null) {
const next = curr.next; // 1. save before we clobber it
curr.next = prev; // 2. reverse the arrow
prev = curr; // 3. advance prev
curr = next; // 4. advance curr
}
return prev; // prev is the new head
}curr.next = prev before saving next, you lose every node after curr with no recovery.When → Problems that ask about the midpoint, whether a cycle exists, or where a cycle starts. One pass, O(1) space.
// Shared node shape (used by all templates below)
interface ListNode {
val: number;
next: ListNode | null;
}
// Fast & slow — find middle, detect cycle, find cycle start
// ── Find middle ──────────────────────────────────────────
function findMiddle(head: ListNode | null): ListNode | null {
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
slow = slow!.next; // slow moves 1 step
fast = fast.next.next; // fast moves 2 steps
}
return slow; // on even-length: the second middle
}
// ── Floyd cycle detection ────────────────────────────────
function hasCycle(head: ListNode | null): boolean {
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
slow = slow!.next;
fast = fast.next.next;
if (slow === fast) return true; // meeting point → cycle
}
return false;
}
// ── Find cycle entry node ────────────────────────────────
function detectCycle(head: ListNode | null): ListNode | null {
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
slow = slow!.next;
fast = fast.next.next;
if (slow === fast) {
// Reset one pointer to head; both advance 1 step to meet at entry
let entry = head;
while (entry !== slow) {
entry = entry!.next;
slow = slow!.next;
}
return entry;
}
}
return null;
}fast !== null must be checked before fast.next !== null. Reversing the order causes a null-pointer crash on odd-length lists.When → Any merge or build problem where the head might change or the list might be empty. The dummy sentinel means the first real node is just another splice step.
// Shared node shape (used by all templates below)
interface ListNode {
val: number;
next: ListNode | null;
}
// Dummy head — merge two sorted lists, O(n + m) time, O(1) space
// Dummy eliminates the "is head null?" special-case on every step.
function mergeTwoLists(
l1: ListNode | null,
l2: ListNode | null,
): ListNode | null {
const dummy: ListNode = { val: 0, next: null }; // sentinel
let tail = dummy;
while (l1 !== null && l2 !== null) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next!;
}
tail.next = l1 ?? l2; // attach the remaining non-empty list
return dummy.next; // NEVER return dummy — return dummy.next
}dummy.next, not dummy →the single most common linked-list submission error is returning the sentinel itself. The sentinel's val is garbage; it exists only to simplify pointer logic.When → Problems that reference a position counted from the end. A dummy head plus an n-gap between the two pointers reaches the target node in a single forward pass.
// Shared node shape (used by all templates below)
interface ListNode {
val: number;
next: ListNode | null;
}
// Two-pointer n-gap — remove nth node from end, O(n) time, O(1) space
// Dummy head handles the edge case where the head itself is removed.
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
const dummy: ListNode = { val: 0, next: head };
let fast: ListNode | null = dummy;
let slow: ListNode | null = dummy;
// Advance fast by n+1 steps so the gap between fast and slow is n
for (let i = 0; i <= n; i++) {
fast = fast!.next;
}
// Move both until fast reaches the end
while (fast !== null) {
fast = fast.next;
slow = slow!.next;
}
// slow is now just before the target node
slow!.next = slow!.next!.next;
return dummy.next;
}slow to stop at the node before the target so you can splice it out. Advancing only n steps lands slow on the target itself, which cannot unlink itself.Always store const next = curr.next as the very first line of a rewiring step — before any assignment to curr.next. Once you overwrite curr.next, the tail of the list is unreachable and cannot be recovered.
The fast pointer advances two steps per iteration. The guard must be fast !== null && fast.next !== null. Checking only fast !== null crashes when the list has even length (fast lands on the last node and fast.next.next dereferences null). Checking only fast.next !== null crashes on an empty list.
You need to stop slow at the node before the one being deleted. With the dummy head in place, advance fast by n + 1 steps so the gap is n and slow lands on the predecessor. Advancing only n steps puts slow on the target node itself, which cannot splice itself out.
When you use a dummy head, the answer is dummy.next, not dummy. Returning the sentinel returns a node with a garbage val of 0 prepended to the real result. This is the most common wrong-answer submission for merge and build problems.