Linked lists — dummy heads + fast/slow

Two tricks cover 80%: a dummy head eliminates edge-case branches, and fast/slow pointers find midpoints and detect cycles in O(1) space.

The on-ramp: what a linked list is, and why bother

An array (Python list) stores its values in one contiguous block of memory, so the machine can compute the address of element i with simple arithmetic — that is why a[5] is instant, or O(1) ("constant time" — the cost does not grow with the size of the list). The price is the opposite operation: inserting or deleting near the front means shifting every later element over by one slot, which is O(n) ("linear time" — cost grows in step with n, the number of elements).

A linked list trades those costs the other way. Because each node is a separate box that merely points to the next, you cannot do address arithmetic — to reach the 5th node you must start at the front and follow arrows five times, which is O(n) access. But if you are already holding the node where you want to splice something in or cut something out, the edit is just a couple of pointer rewires: O(1) insert/delete, with no shifting. That single trade-off — O(n) to find, O(1) to edit once found — is the whole reason linked lists exist and the reason interview problems about them are really pointer-juggling puzzles.

Vocabulary, defined inline

Every linked-list problem is built from the same handful of words. Pin them down once and the rest is mechanical.

• Node — one box in the chain. It holds a value (often called val) and at least one link. A minimal node is just { val, next }.
• Pointer / reference — the arrow itself: a variable that does not hold a value but holds the location of a node. In Python and TypeScript there are no raw memory addresses; a "pointer" here is simply a variable bound to a node object. Setting a.next = b means "make a's arrow point at the same node b refers to." Two variables can point at the same node — that is the source of most bugs and most cleverness.
• Head — the variable that points at the first node; your only handle on the whole list. Lose the head with no other reference and the list is unreachable (garbage-collected).
• Tail — the last node, whose next is None/null. The None at the end is the sentinel value that tells a traversal "stop."
• Singly linked — each node has exactly one link, next, so you can only travel forward. Doubly linked — each node also carries a prev link back to the node before it, so you can walk both directions and delete a node without first finding its predecessor; the cost is an extra pointer per node to keep in sync.
• Dummy / sentinel node — a throwaway node you place before the real head so that "the first node" is never a special case. Its value is ignored; only its next matters. Return dummy.next at the end.
• Traversal — walking the chain from the head, one next at a time, until you hit None. The canonical loop is while node: ... node = node.next.
• In-place reversal — flipping every arrow to point backward without allocating a new list, reusing the existing nodes. "In place" means O(1) extra space.
• Two-pointer / runner technique — moving two pointers through the same list at different speeds or with a fixed gap between them. The fast/slow ("tortoise and hare") variant moves one pointer two steps for every one step of the other.

Defining the node

Before any algorithm, you need the box itself. Both languages define a node as a tiny object with a value and a link that defaults to "nothing." This is exactly the ListNode the templates below assume.

# Python — a node is a value plus a forward link
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val        # the data this box holds
        self.next = next       # arrow to the following node, or None at the tail

To build 1 → 2 → 3 by hand you chain three of them: a = ListNode(1, ListNode(2, ListNode(3))). The outermost node is the head; the innermost node's next is the default None, marking the tail.

Traversal: the loop everything is built on

Every linked-list routine is a variation on one walk. You start at the head and keep hopping to .next until the pointer becomes None. Read the loop as "while there is still a node, do something, then step forward."

# Count the nodes — the simplest possible traversal
def length(head):
    count, node = 0, head
    while node:               # stops when node is None (we walked off the tail)
        count += 1
        node = node.next       # hop to the next box
    return count

Notice we copy head into a throwaway variable node first. If we walked head itself forward, we would lose our handle on the start of the list. Never advance the only pointer you have to the front.

Template — Reverse Linked List

def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev, curr = curr, nxt
    return prev

function reverse(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null, curr = head;
  while (curr) {
    const nxt = curr.next;
    curr.next = prev;
    prev = curr; curr = nxt;
  }
  return prev;
}

A fully traced reversal of 1 → 2 → 3

The walkthrough above showed the boxes; here is the same reversal as a table of the three variables at the top of every loop iteration, so you can see exactly what each line of the template does. Read each row as "this is the state right after that iteration's four statements ran." · means the node it points at; ∅ means None.

# Start:  prev = ∅ ,  curr = 1 ,  list is 1 → 2 → 3
#
# iter 1:  nxt = curr.next        -> nxt  = 2   (save the rest BEFORE we cut)
#          curr.next = prev       -> 1.next = ∅  (node 1 now points back at nothing)
#          prev, curr = curr, nxt -> prev = 1 ,  curr = 2
#          chain so far:  ∅ ← 1      2 → 3
#
# iter 2:  nxt = curr.next        -> nxt  = 3
#          curr.next = prev       -> 2.next = 1  (node 2 now points back at 1)
#          prev, curr = curr, nxt -> prev = 2 ,  curr = 3
#          chain so far:  ∅ ← 1 ← 2    3
#
# iter 3:  nxt = curr.next        -> nxt  = ∅
#          curr.next = prev       -> 3.next = 2  (node 3 now points back at 2)
#          prev, curr = curr, nxt -> prev = 3 ,  curr = ∅
#          chain so far:  ∅ ← 1 ← 2 ← 3
#
# curr is ∅ -> loop ends. return prev = 3.  New list: 3 → 2 → 1.

The single most important line is the first one of each iteration. The moment we run curr.next = prev, the original forward arrow is overwritten — so if we had not stashed nxt = curr.next a line earlier, the tail of the list would be orphaned and unreachable. Save first, then cut.

The dummy-node trick, spelled out

Why the trick earns its keep: in any routine that deletes or inserts nodes, the front of the list is dangerous because it has nothing in front of it. If you want to delete a middle node, you grab the node before it and set before.next = before.next.next — clean. But the head has no "before," so deleting it normally needs a separate branch (head = head.next). A dummy node manufactures a "before" for the real head, so the head stops being special and one piece of code handles every position.

# Remove every node equal to target, including a head that matches.
def remove_all(head, target):
    dummy = ListNode(0, head)   # sentinel sits BEFORE the real head
    prev = dummy
    while prev.next:
        if prev.next.val == target:
            prev.next = prev.next.next  # splice the node out — works even at the head
        else:
            prev = prev.next
    return dummy.next               # the real head, even if the old one was removed

Returning dummy.next instead of head is what makes this robust: if the original head was deleted, head would be a stale pointer to a removed node, but dummy.next always names whatever node is genuinely first when you finish.

Fast/slow pointers: middle and cycle in one pass

The two-pointer runner technique answers two classic questions without a length count and without extra memory. Move slow one step and fast two steps per loop. When fast reaches the end, slow has covered exactly half the distance — so it sits on the middle node. And if the list secretly loops back on itself (a cycle), the fast pointer eventually laps the slow one and they collide — Floyd's cycle detection.

# Middle of the list: when fast falls off the end, slow is the midpoint.
def middle(head):
    slow = fast = head
    while fast and fast.next:   # guard BOTH so fast.next.next is safe
        slow = slow.next         # one step
        fast = fast.next.next    # two steps
    return slow

# Cycle detection: if there is a loop, fast and slow must meet inside it.
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:        # same node object -> they collided -> cycle
            return True
    return False          # fast hit None -> the list has an end -> no cycle

The condition while fast and fast.next is the linchpin and a frequent crash site. You write fast.next.next inside the loop, so you must first prove that both fast and fast.next exist; checking only fast would let fast.next.next blow up on the last node.

Recognition signals — reach for these patterns when…

• The problem hands you a head and talks about next pointers, "in place," or "without extra space" — almost always pointer rewiring, not rebuilding.
• It mentions the middle, the n-th from the end, or a cycle / loop — fast/slow or a fixed-gap two-pointer.
• It says reverse, or reverse a sub-section, or reverse in groups of k — the prev/curr/nxt flip is the building block.
• It deletes or merges and the head might change — add a dummy node and return dummy.next.
• You only need O(1) extra space and a single pass — that constraint is the loudest hint that a clever pointer trick, not an array copy, is intended.

Pitfalls — the bugs that bite everyone

Merge two sorted lists — the core pointer dance from this lesson: