The dummy head

One fake node at the front, and every special case about the head disappears.

Key idea

Why the head keeps needing special treatment

Every operation that changes the front of a list needs its own branch, because the head has no predecessor to rewire through. The last lesson had two of those branches in one short function.

The fix is to invent a predecessor. Create one throwaway node that sits before the real head, do all the work through it, and return its next at the end. The head is now an ordinary node with something before it, and the special cases vanish.

1class Node:2    def __init__(self, val, next=None):3        self.val, self.next = val, next4 5def build(values):6    head = None7    for value in reversed(values):8        head = Node(value, head)9    return head10 11def to_list(node):12    out = []13    while node:14        out.append(node.val)15        node = node.next16    return out17 18def remove_all(head, target):19    dummy = Node(0, head)          # a node that is always before everything20    prev = dummy21    while prev.next:22        if prev.next.val == target:23            prev.next = prev.next.next   # skip, prev stays put24        else:25            prev = prev.next26    return dummy.next              # the real head, whatever it turned out to be27 28print(to_list(remove_all(build([1, 2, 6, 3, 6]), 6)))29print(to_list(remove_all(build([7, 7]), 7)))30print(to_list(remove_all(build([]), 7)))

Why it works

The other use: building a list

The same trick works when producing a list rather than editing one. Start with a dummy, keep a tail pointer at the last node appended, and attach each new node to tail.next.

Without it, the first append is a special case because there is no tail yet. With it, there always is.

1class Node:2    def __init__(self, val, next=None):3        self.val, self.next = val, next4 5def build(values):6    head = None7    for value in reversed(values):8        head = Node(value, head)9    return head10 11def to_list(node):12    out = []13    while node:14        out.append(node.val)15        node = node.next16    return out17 18def evens_only(head):19    dummy = Node(0)20    tail = dummy21    while head:22        if head.val % 2 == 0:23            tail.next = Node(head.val)24            tail = tail.next25        head = head.next26    return dummy.next27 28print(to_list(evens_only(build([1, 2, 3, 4, 5, 6]))))29print(to_list(evens_only(build([1, 3]))))

Quick check· 5 min

What does the dummy head remove?

Which of these problems does a dummy head actually solve?

The head has no predecessor, so operations that change the front need their own branchTraversal can run off the end of the list into NoneLinked lists cannot be traversed backwardThe list length is not stored, so counting requires a full pass

Problem· 20 min

Merge Two Sorted Lists

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1class Node:2 def __init__(self, val, next=None):3 self.val, self.next = val, next4 5def build(values):6 head = None7 for value in reversed(values):8 head = Node(value, head)9 return head10 11def to_list(node):12 out = []13 while node:14 out.append(node.val)15 node = node.next16 return out17 18def remove_all(head, target):19 dummy = Node(0, head) # a node that is always before everything20 prev = dummy21 while prev.next:22 if prev.next.val == target:23 prev.next = prev.next.next # skip, prev stays put24 else:25 prev = prev.next26 return dummy.next # the real head, whatever it turned out to be27 28print(to_list(remove_all(build([1, 2, 6, 3, 6]), 6)))29print(to_list(remove_all(build([7, 7]), 7)))30print(to_list(remove_all(build([]), 7)))

1class Node:2 def __init__(self, val, next=None):3 self.val, self.next = val, next4 5def build(values):6 head = None7 for value in reversed(values):8 head = Node(value, head)9 return head10 11def to_list(node):12 out = []13 while node:14 out.append(node.val)15 node = node.next16 return out17 18def evens_only(head):19 dummy = Node(0)20 tail = dummy21 while head:22 if head.val % 2 == 0:23 tail.next = Node(head.val)24 tail = tail.next25 head = head.next26 return dummy.next27 28print(to_list(evens_only(build([1, 2, 3, 4, 5, 6]))))29print(to_list(evens_only(build([1, 3]))))