← All patternsDummy Head and Merging · template
Pattern · Linked Lists
Dummy Head and Merging
Start with a fake node before the real head so building, merging and deleting never need special cases for the first node.
Time O(n + m) · Space O(1)
Taught in Module 8: Linked Lists
Think of it like this
A placeholder bookmark at the start of a shelf: you always have something to attach the first real book to.
Clues that point here
- → Merge two sorted lists
- → Delete nodes (the head might be deleted)
- → Build a new list while scanning
- → Partition a list
Not this pattern when
- ✕ You only read the list without changing links
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
ListNode dummy = new ListNode(0), tail = dummy;
while (a != null && b != null) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = (a != null) ? a : b; // attach whatever is left
return dummy.next;Common versions
- Merge two sorted lists
- Remove Nth node from end
- Remove linked list elements
- Add two numbers
- Partition list
Practice problems with this pattern
8.4Merge Two Sorted ListsEasymain pattern8.5Remove Nth Node From EndMediummain pattern8.6Add Two NumbersMediummain pattern8.8Reorder ListMediumalso uses it8.9Merge K Sorted ListsHardalso uses it