Sentinel (Dummy) Head & Merging

Foundations

In the first lesson, reversing changed which node was the head, and prev started at None to handle the first one. Now, what if you build a list node by node, or delete nodes, and the head itself is what might change?

A sentinel, or dummy, node is a placeholder placed before the real head. With dummy.next = head, every real node has a node before it, so deleting the first node or appending to an empty list is the same code as any other position: rewire the previous node's .next. A tail reference marks the last node attached so far, and the finished list is dummy.next.

Merge the sorted runs 1 → 5 → 7 and 3 → 6, built from nums = [7, 1, 5, 3, 6]. Start tail at the dummy. Attaching 1 first is the same step as every later one: set tail.next, then move tail to the new node. Then 3, 5, and 6 attach; when the second run is used up, one link attaches 7. The answer is dummy.next: 1 → 3 → 5 → 6 → 7.

• Two-Pointer Merge Passes

  This is the same merge, done with .next links instead of indexes.

  Open lesson

Case Scenario

Merge Two Sorted Lists gives the heads of two sorted lists, list1 and list2, and asks for one sorted list spliced from their nodes. Either list may be empty, and either may supply the head, which is exactly the case the dummy removes. For list1 = [1, 2, 4] and list2 = [1, 3, 4], the merged list is 1 → 1 → 2 → 3 → 4 → 4.

The direct approach collects all m + n values, sorts them, and builds new nodes: O((m + n) log(m + n)) time and a fresh node for every value. It ignores that both lists were already sorted. And a hand-written splice without a dummy needs separate code for choosing the head and for an empty input, which is where most bugs hide.