Linked Lists
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.
Tip
Compare that with the previous version
The earlier version needed a separate loop for leading matches, a prev that might be None, and care about when to advance. This one has a single loop, prev is never None, and the advance rule is obvious.
It also handles the empty list without a check, because dummy.next is None and the loop simply does not run. Whenever a list function is accumulating branches around the head, reach for this before adding another one.
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.
Tip
Reusing nodes rather than creating them
The version above allocates a new node per kept element. Many problems instead want you to relink the existing nodes, which uses no extra memory.
Relinking is tail.next = head followed by advancing both, and it needs one extra care: when you finish, the last node you attached may still point at nodes you did not want, so terminate the result with tail.next = None. Forgetting that is a common source of lists that appear to contain elements you filtered out.
Key idea
Merging two sorted lists
With a dummy head and a tail, merging is a loop that repeatedly attaches whichever of the two current nodes is smaller, then advances that list.
When one list runs out, the rest of the other can be attached in a single step rather than node by node, because it is already in order and already linked. That last detail is worth knowing: it turns a trailing loop into one assignment.
What does the dummy head remove?
Which of these problems does a dummy head actually solve?
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.