Linked List

Linked list work is pointer discipline. Most bugs come from losing a reference or mis-connecting a node. Use dummy heads to simplify edge cases and write down the invariant before you start.

Pattern A: Dummy head for merges/removals

Use when: you may remove or insert at the head.

Invariant: dummy.next always points to the current list head.

Skeleton:

dummy = new Node(0)
dummy.next = head
prev = dummy
for each node:
    if should remove node: prev.next = node.next
    else: prev = node
return dummy.next

Problems:

• merge-two-sorted-lists.
• remove-nth-node-from-end-of-list.

Pattern B: Fast/slow pointers

Use when: you need a cycle check or relative positions.

Invariant: fast moves 2 steps, slow moves 1 step.

Skeleton (cycle detection):

slow = head; fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast: return true
return false

Skeleton (cycle entry):

meet = slow
p1 = head; p2 = meet
while p1 != p2:
    p1 = p1.next
    p2 = p2.next
return p1

Problems:

• linked-list-cycle.
• linked-list-cycle-ii.

Pattern C: Iterative reversal

Use when: reversing the entire list or a segment.

Invariant: prev is the reversed prefix; cur is the next node to process.

Skeleton (full reverse):

prev = nil
cur = head
while cur:
    next = cur.next
    cur.next = prev
    prev = cur
    cur = next
return prev

Skeleton (reverse sublist [m..n]):

prev = node before sublist
cur = prev.next
for i in 0..(n-m-1):
    move = cur.next
    cur.next = move.next
    move.next = prev.next
    prev.next = move

Problems:

• reverse-linked-list.
• reverse-linked-list-ii.
• reverse-nodes-in-k-group (apply segment reversal in chunks).

Pattern D: Digit-wise addition

Use when: lists represent reversed digits.

Invariant: carry holds the sum overflow for the next digit.

Skeleton:

carry = 0
while l1 or l2 or carry:
    sum = val(l1) + val(l2) + carry
    carry = sum / 10
    append(sum % 10)

Problems:

• add-two-numbers.

Pattern E: Copy list with random pointers

Use when: each node has an extra random pointer.

Invariant: every original node maps to exactly one new node.

Skeleton (hash map):

for node in list: map[node] = new Node(node.val)
for node in list:
    map[node].next = map[node.next]
    map[node].random = map[node.random]

Problems:

• copy-list-with-random-pointer.

Pattern F: LRU cache (hash + doubly list)

Use when: you need O(1) get/put with eviction.

Invariant: most-recent item is near head; least-recent near tail.

Skeleton:

get(key): if not found return -1; move node to front
put(key, value):
    if exists: update + move to front
    else: insert new at front; if size > cap: evict tail

Problems:

• lru-cache.

When to use Linked List techniques (checklist)

• You must do O(1) insertions/deletions in the middle.
• Two-pointer distance logic is required (cycle, kth from end).
• You need in-place reversal without extra arrays.

Common failures (checklist)

• Losing the remainder of the list when rewiring pointers.
• Forgetting to handle head changes (use a dummy).
• Not reconnecting the tail after reversing a segment.
• Off-by-one when counting k-group sizes.

Problem mapping

• linked-list-cycle: fast/slow detection.
• linked-list-cycle-ii: detect and locate cycle entry.
• add-two-numbers: digit-wise simulation with carry.
• merge-two-sorted-lists: dummy head merge.
• copy-list-with-random-pointer: map or interleave.
• reverse-linked-list: iterative reversal.
• reverse-linked-list-ii: reverse sublist in-place.
• reverse-nodes-in-k-group: chunk reversal with size check.
• remove-nth-node-from-end-of-list: two pointers + dummy.
• lru-cache: hash map + doubly list.