Linked lists: the dummy node and the two-pointer dance

The list is almost never the point. The point is that you can only move forward, one node at a time, and you must never lose your only reference to the rest of the chain. Two idioms — a sentinel head and a pair of pointers — fall out of that single constraint and solve nearly every list problem.

What a linked list is, and why it trades the way it does

A linked list is the simplest pointer-based structure. An array stores elements in one contiguous block, so it has O(1) random access but O(n) insertion/deletion in the middle (everything after the gap shifts). A linked list trades that the other way: each element ("node") holds a value plus a reference to the next node. There is no contiguous block — nodes can live anywhere in memory, wired together by pointers.

[3|·]──>[7|·]──>[1|·]──>[9|/]      (/ = None, the end)

The consequence is a clean swap of costs:

• O(1) insert/delete given a pointer to the spot — just rewire next links.
• O(n) access by index — you must walk from the head; there is no arithmetic shortcut.

So linked lists shine when you splice and reorder nodes a lot and rarely index by position.

Invariants — the rules of the game

• head is your only handle to the whole list. Lose it and you leak the list.
• Each node knows only its next. To delete or insert you need the node before the target — a singly linked list cannot look backward.
• Reaching node i costs i hops. Plan pointer movement carefully.

The two idioms that solve 90% of list problems

(1) The dummy (sentinel) head node

Allocate a throwaway node whose next is the real head. Now every node — including the original head — has a predecessor. This kills the special case "what if I delete/insert at the head?" You build off dummy.next and return dummy.next at the end. Whenever a result list's head might change or be removed, reach for a dummy.

(2) Two pointers (fast/slow, or a fixed gap)

Walk two pointers at different speeds or with a fixed distance between them. In one pass you can find the middle (fast goes 2×, slow goes 1×; slow lands on the middle), detect a cycle (Floyd), or find the nth-from-end node (advance one pointer n steps first, then move both until the leader hits the end). These are all O(n) time, O(1) extra space.

The node

A singly linked list is just a chain of these. There is no separate "list" object — a list is its head node (or None for empty).

class ListNode:
    def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
        self.val = val
        self.next = next

    def __repr__(self) -> str:  # handy when debugging in a REPL
        return f"ListNode({self.val})"

Two test helpers make the rest legible. Notice that build already uses the dummy idiom we are about to teach — keeping a tail pointer makes append O(1) and avoids the "first node is special" branch.

def build(values: List[int]) -> Optional[ListNode]:
    dummy = ListNode()          # sentinel; dummy.next becomes the real head
    tail = dummy
    for v in values:
        tail.next = ListNode(v)  # O(1) append because we keep a tail pointer
        tail = tail.next
    return dummy.next            # real head (or None if values was empty)

def to_list(head: Optional[ListNode]) -> List[int]:
    out: List[int] = []
    node = head
    while node is not None:
        out.append(node.val)
        node = node.next
    return out

Reverse a linked list (LeetCode 206)

Walk the list flipping each node's next to point backward. The only trick is that you must save the next node before you overwrite the pointer, or you lose the rest of the chain. Three pointers do it: prev (head of the already-reversed portion, starts None), curr (the node we are flipping now), and nxt (a stash of curr.next).

def reverse_iterative(head: Optional[ListNode]) -> Optional[ListNode]:
    prev: Optional[ListNode] = None
    curr = head
    while curr is not None:
        nxt = curr.next     # 1. save the rest of the list
        curr.next = prev    # 2. flip this node's link backward
        prev = curr         # 3. advance the reversed-portion head
        curr = nxt          # 4. advance into the saved rest
    return prev             # prev is the new head (old tail)

The recursive version reverses everything after head, then makes head's successor point back to head. The recursion bubbles the original tail up as the new head.

def reverse_recursive(head: Optional[ListNode]) -> Optional[ListNode]:
    if head is None or head.next is None:
        return head
    new_head = reverse_recursive(head.next)  # reverse the tail; returns old end
    head.next.next = head   # the node after head now points back to head
    head.next = None        # head becomes the new tail
    return new_head

Cycle detection — Floyd's tortoise & hare (LeetCode 141 / 142)

Send a slow pointer (1 hop) and a fast pointer (2 hops). If there is no cycle, fast falls off the end (None). If there is a cycle, fast keeps lapping inside the loop and must eventually land on slow — like two runners on a circular track, the faster one laps the slower.

def has_cycle(head: Optional[ListNode]) -> bool:
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next        # 1 step
        fast = fast.next.next   # 2 steps
        if slow is fast:        # identity, not value — same node object
            return True
    return False

To find where the cycle begins, use Floyd's two-phase trick. After slow and fast meet inside the loop, it is a number-theory fact that the distance from the list head to the cycle start equals the distance from the meeting point to the cycle start (both measured forward, mod the loop length). So reset one pointer to the head and advance both one step at a time; they meet exactly at the cycle entrance.

def detect_cycle_start(head: Optional[ListNode]) -> Optional[ListNode]:
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:                 # phase 1: found a meeting point
            ptr = head
            while ptr is not slow:       # phase 2: march to the entrance
                ptr = ptr.next
                slow = slow.next
            return ptr
    return None                          # no cycle

Find the middle — fast/slow (LeetCode 876)

When fast moves twice as fast as slow, slow is at the halfway mark when fast reaches the end. For even length this returns the second middle (LeetCode's convention), because the loop condition checks fast.next. This middle-finder is the first step of merge sort on lists and of the palindrome check below.

def find_middle(head: Optional[ListNode]) -> Optional[ListNode]:
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

Merge two sorted lists (LeetCode 21)

A standard two-pointer merge. The dummy head shines here: we do not know which list owns the smaller first element, so a sentinel lets us append uniformly and just return dummy.next. We splice existing nodes rather than allocate, so it is O(1) extra space.

def merge_two_sorted(l1: Optional[ListNode],
                     l2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode()
    tail = dummy
    while l1 is not None and l2 is not None:
        if l1.val <= l2.val:
            tail.next = l1      # splice l1's node in
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    tail.next = l1 if l1 is not None else l2  # attach whatever's left
    return dummy.next

Remove the nth node from the end — fixed-gap two pointers (LeetCode 19)

We cannot index from the end in a singly linked list, but we can create a fixed gap of n nodes between a lead and a lag pointer. Advance lead n steps first; then move both until lead falls off the end. Now lag sits on the node just before the target, ready to splice it out. The dummy head handles "remove the head itself" (when n equals the length) without a special branch — lag starts on dummy, so lag.next can be the real head.

def remove_nth_from_end(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    lead = lag = dummy
    for _ in range(n):              # open a gap of n between lead and lag
        lead = lead.next
    while lead.next is not None:    # walk both until lead is on the last node
        lead = lead.next
        lag = lag.next
    lag.next = lag.next.next        # lag is the predecessor; skip the target
    return dummy.next

Palindrome linked list (LeetCode 234)

This problem composes three idioms: (1) fast/slow to find the middle, (2) reverse the second half in place, (3) walk both halves comparing values. Reversing rather than copying to an array is what makes it O(1) space.

def is_palindrome(head: Optional[ListNode]) -> bool:
    if head is None or head.next is None:
        return True
    # 1. find middle (slow ends at start of second half for even length)
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    # 2. reverse the second half
    second = reverse_iterative(slow)
    # 3. compare halves; first half may have one extra node (odd length) — fine,
    #    we stop when the (shorter) reversed half is exhausted.
    p, q = head, second
    ok = True
    while q is not None:
        if p.val != q.val:
            ok = False
            break
        p = p.next
        q = q.next
    return ok

Reorder list (LeetCode 143)

Transform L0→L1→…→Ln into L0→Ln→L1→Ln-1→…. This is the canonical "compose three idioms" problem: (1) find the middle, (2) reverse the second half, (3) zip-merge the two halves alternately.

def reorder_list(head: Optional[ListNode]) -> Optional[ListNode]:
    if head is None or head.next is None:
        return head
    # 1. middle
    slow = fast = head
    while fast.next is not None and fast.next.next is not None:
        slow = slow.next
        fast = fast.next.next
    # 2. split + reverse second half
    second = reverse_iterative(slow.next)
    slow.next = None                # cut the first half loose
    first = head
    # 3. weave: take from first, then second, alternately
    while second is not None:
        f_next, s_next = first.next, second.next
        first.next = second
        second.next = f_next
        first = f_next
        second = s_next
    return head

The self-checks confirm the patterns hold end to end, e.g. to_list(reorder_list(build([1, 2, 3, 4, 5]))) == [1, 5, 2, 4, 3] and detect_cycle_start returns the exact node a tail was wired back to.