Pointer Surgery & Dummy Nodes

What a linked list actually is

A linked list is a chain of nodes, where each node holds a value and a pointer (a reference) to the next node. There are no indexes: to reach the 500th node you follow 500 pointers. In exchange, splicing a node in or out is a single pointer rewrite — no shifting, unlike arrays.

That trade shapes every interview problem: list questions are rarely about finding things (that is O(n) no matter what) and almost always about rewiring pointers in place without losing part of the chain. Think of it as surgery: cut carefully, and never let go of a piece you still need.

The one bug that causes most failures

The number one linked-list bug is overwriting .next before saving what it pointed to. The moment you write cur.next = something, the old cur.next chain is unreachable — gone. The fix is a habit: save first, then cut.

Reversal: the prev/cur/next dance

Reversing a list means flipping every arrow. Three pointers walk the list together:

def reverse(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next      # 1. save the rest of the list
        cur.next = prev     # 2. flip this arrow backwards
        prev = cur          # 3. step prev forward
        cur = nxt           # 4. step cur forward (using the saved pointer)
    return prev             # cur is None; prev is the new head

Trace on 1 -> 2 -> 3:

Mid-reversal the list is genuinely split in two: a reversed front (prev) and an untouched rear (cur). That is fine — nxt is the lifeline that reconnects you each iteration. Memorize this loop until you can write it while talking; it is a building block inside at least five harder problems.

Dummy nodes: deleting edge cases instead of handling them

A dummy head (also called a sentinel) is a throwaway node you place before the real head: dummy.next = head. Why bother? Because the head is the one node with no predecessor, and any operation that might modify or remove the head needs special-case code — unless you give the head a predecessor.

Merging two sorted lists shows it best:

def merge(l1, l2):
    dummy = ListNode()
    tail = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next, l1 = l1, l1.next
        else:
            tail.next, l2 = l2, l2.next
        tail = tail.next
    tail.next = l1 or l2    # splice on whatever remains
    return dummy.next

No "is the result empty? which list starts?" branching — the first real node simply lands after dummy, and dummy.next is the answer. The same trick makes Remove Nth Node From End clean: start your pointers from dummy, and removing the actual head becomes the same code path as removing any other node.

Rule of thumb: if an operation could touch or replace the head, use a dummy.

Offset pointers: the n-from-the-end gap

To find the nth node from the end in one pass, run two pointers with a fixed gap: advance fast n steps first, then move fast and slow together until fast runs off the end. The gap never changes, so slow lands exactly n from the end. To delete that node you want slow one step earlier — which is exactly what starting slow at the dummy gives you.

Compound operations: hard problems are combos

Almost every "hard" list problem is two or three memorized moves glued together. The canonical example is Reorder List (1 -> 2 -> 3 -> 4 -> 5 becomes 1 -> 5 -> 2 -> 4 -> 3):

1. Find the middle with slow/fast pointers (slow moves 1, fast moves 2; when fast hits the end, slow is at the middle — details next lesson).
2. Reverse the second half with the prev/cur/next dance.
3. Interleave the two halves, alternating one node from each.

Each piece is something you already know; the skill is decomposition. Same story elsewhere: Palindrome Linked List = find middle + reverse + compare. Sort List = find middle + recurse + merge. Add Two Numbers is a zipper walk with a carry variable — remember the final if carry: append 1 for inputs like 999 + 1.

Two hygiene rules for combos: after splitting a list, null-terminate the front piece (forgetting creates accidental cycles), and after interleaving, make sure the final node's .next is None.

LRU Cache: two structures, one design

The most asked design problem, LRU (Least Recently Used) Cache, is a marriage of exactly the two structures you now know:

• A hash map from key to node — O(1) lookup.
• A doubly linked list of nodes in recency order — O(1) removal and O(1) insertion at the front, because a doubly linked node knows both neighbors and can unsplice itself.

Every get or put moves the touched node to the front (most recent). On overflow, evict the back node — and remember to delete it from the map too. Dummy nodes appear again: a permanent dummy head and dummy tail mean insert-at-front and remove-at-back never special-case an empty list.

Neither structure alone works: the map has no order, the list has no fast lookup. Interviewers ask it precisely because it tests whether you can compose structures — the same skill as the combo problems above.