Algorithms / Linked List Dummy Nodes
Least You Need to Know: Dummy Nodes, Head Cases, and Stable Stitching
A dummy node is a fake node placed before the real head so that insertion and deletion at the front look like ordinary middle-of-list operations. Interviews love dummy nodes because they remove special-case branching and make stitched-together outputs easier to reason about.
The least you need to know
- A dummy node sits before the real answer list and is not part of the final output.
- Returning `dummy.next` often avoids special cases around the first real node.
- Dummy nodes simplify merges, filtered rebuilds, and partitioning tasks.
- A tail pointer commonly tracks the last node already built in the output list.
- Stable stitching means nodes keep their relative order when the problem requires it.
Key notation
dummy
sentinel node before the real result
tail
last node already attached to the built list
dummy.next
real head of the constructed answer
Tiny worked example
- To merge two sorted lists, start with a dummy node and a `tail` pointer at the dummy.
- Each time you choose the smaller front node, attach it to `tail.next` and advance `tail`.
- After one list empties, attach the whole remaining suffix of the other list.
- Finally return `dummy.next`.
Common mistakes
- Students sometimes accidentally return the dummy itself instead of `dummy.next`.
- Students sometimes forget to advance `tail` after attaching a node.
- A dummy node simplifies cases but does not replace the need for correct comparisons.
How to recognize this kind of problem
- The prompt has awkward head-edge cases for insertion, deletion, merge, or partition.
- You are building a new list incrementally from left to right.
- A sentinel before the first real node would make all splice operations look uniform.