Lesson 21 — The dummy node trick

~20 minutes · dummy node · Python · Day 23

Linked-list interview problems often become messy at the head of the list. In Merge Two Sorted Lists, the first node of the answer is especially annoying: before it exists, where do you attach the first real node? The dummy node trick gives you one fake starting point so every real attachment follows the same rule.

The invariant

A fake head node means the real first node is never a special case, so the loop body handles every node the same way.

Merge Two Sorted Lists: the slow way first

The problem gives two sorted linked lists and asks for one sorted linked list. A linked list is a chain of nodes where each node points to the next one (Wikipedia: linked list). The brute-force approach is to copy all values into a Python list, sort them, then build a new linked list. That is O((m+n) log(m+n)) time because sorting dominates (Python wiki: time complexity), and O(m+n) extra space for the copied values and new nodes.

def mergeTwoLists(list1, list2):
    vals = []
    while list1:
        vals.append(list1.val)
        list1 = list1.next
    while list2:
        vals.append(list2.val)
        list2 = list2.next
    vals.sort()
    head = tail = None
    for x in vals:
        node = ListNode(x)
        if head is None:
            head = tail = node
        else:
            tail.next = node
            tail = node
    return head

This works, but it throws away the useful fact that the two input lists are already sorted. It also has a noisy if head is None branch just to create the first real node. If the front nodes are 1 and 3, the next answer node must be 1. No full sort is needed; only compare the two current heads.

Merge Two Sorted Lists: the dummy way

Make one fake head, then keep a tail pointer at the end of the answer you have built so far. Each loop compares the two current nodes, attaches the smaller one after tail, advances that input list, and then moves tail forward. At the end, attach the leftover list. LeetCode's starter code supplies the ListNode shape for this problem (LeetCode: Merge Two Sorted Lists).

The dummy node is a fixed anchor; the first real node and every later node use the same tail.next attachment.

def mergeTwoLists(list1, list2):
    dummy = ListNode()               # fake head, not part of answer
    tail = dummy                     # last node in answer so far
    while list1 and list2:
        if list1.val <= list2.val:
            tail.next = list1; list1 = list1.next
        else:
            tail.next = list2; list2 = list2.next
        tail = tail.next             # move to the node just attached
    tail.next = list1 or list2       # one sorted suffix remains
    return dummy.next                # skip the fake head

The dummy node never enters the answer. It only gives tail.next a safe place to write on the very first attachment. Returning dummy.next drops the fake node and keeps every real node.

Transfer: same trick, new costume

Suppose the task is: delete the first node whose value equals target. The awkward case is when the head itself must be deleted. Before opening the reveal, predict the shape: where should prev start, what should it point around, and what should the function return?

def delete_first(head, target):
    dummy = ListNode(0, head)
    prev, cur = dummy, head
    while cur:
        if cur.val == target:
            prev.next = cur.next
            break
        prev, cur = cur, cur.next
    return dummy.next

What the trade buys you

The win is not only speed. The dummy node also removes the fragile branch that says, “if the answer is still empty, set the head differently.” One loop rule handles the first real node and every later node.

Practice — answer before you scroll past

Your move (tonight)

Solve this on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:

1. Merge Two Sorted Lists — predict the brute force first, then code the dummy-node merge from the invariant.

For the encode step, write why dummy.next is the returned answer and why the real head never needs its own branch.

Stuck or curious? Ask your teacher (the agent) — that's what it's for.