Dummy node [mp]

Micro pattern¶

Description¶

Place a stable node before a changing list head so pointer operations do not need a special head case.

Problems¶

Construct a result list¶

Append or insert nodes after a dummy while retaining the result head.

• 21. Merge Two Sorted Lists (Top Easy)
• 2. Add Two Numbers (Top Medium)
• 23. Merge k Sorted Lists (Top Hard)
• 148. Sort List (Top Hard)
• Top-down merge sort linked list (DSA)
• Bottom-up merge sort linked list (DSA)
• Insertion sort linked list (DSA)

Simplify deletion of the head¶

Start traversal at a dummy so the removed node always has a predecessor.

• 19. Remove Nth Node From End of List (Top Easy)

Delimit both ends¶

Use two dummy nodes to remove empty-list and end-point special cases.

• 146. LRU Cache (Top Hard)