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.
Least you need to know
- A dummy node sits before the real answer list and is not part of the final output.
- Returning
dummy.nextoften 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
Worked example
- To merge two sorted lists, start with a dummy node and a
tailpointer at the dummy. - Each time you choose the smaller front node, attach it to
tail.nextand advancetail. - 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
tailafter attaching a node. - A dummy node simplifies cases but does not replace the need for correct comparisons.
How to recognize it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Linked-List Pointer Updates and Local Rewiring.
Least You Need to Know: Linked-List Pointer Updates and Local RewiringRelated lessons
Keep going with nearby lessons in the same topic.