Dummy Node Pattern

A dummy node is an extra node placed before the real list: dummy -> head -> 1 -> 2 -> 3 -> null. Its value is irrelevant. Its job is to guarantee that every real node has a previous pointer available, even if the real node is currently the head.

This turns head mutations into ordinary middle mutations. Instead of asking whether the node to delete is head, you keep prev at the node before curr. At the front, that node is simply dummy.

Without a dummy node, deleting the first real node often requires a separate branch that updates head directly. Deleting later nodes updates prev.next. Two branches mean more code and more chances to forget one path.

With a dummy node, the deletion rule is always the same: when curr should be removed, set prev.next = curr.next. If curr was the original head, this updates dummy.next. Returning dummy.next gives the possibly changed head.

The dummy pattern is common in merge, remove-elements, partition, and k-group problems. Merge builds a result list by appending to a moving tail that starts at dummy. Remove-elements scans with prev and curr. Partition appends nodes into before and after chains that each start with a sentinel.

Reverse-nodes-in-k-group also benefits from a dummy because each reversed group may begin at the current head of the remaining list. The group can be reattached through a stable predecessor instead of constantly checking whether the overall head changed.

The dummy node does not remove the need for careful pointer order. When splicing, preserve the next node before moving curr if the later code still needs it. When appending to a result list, advance the tail after linking the chosen node. When partitioning, terminate the final chain so an old next pointer does not create a hidden cycle.

The benefit is uniformity. Once dummy exists, your algorithm can focus on one invariant: prev always points to the node before the part being examined or rewritten.