Merge Two Sorted Lists — The Bakery Tickets

Boss 2: The Bakery Tickets

After Boss 1's careful flip surgery, this one feels like a breather. It is. But it introduces a tool you'll use in half of the remaining bosses, so don't skim: the dummy node.

The story

Your favorite bakery got popular. Two entrances now, two queues, and a ticket machine at each door. Both queues are sorted by ticket number, lowest in front.

Queue A:  1 → 2 → 4
Queue B:  1 → 3 → 4

The owner wants one line at the counter, still fully sorted:

1 → 1 → 2 → 3 → 4 → 4

You're on queue duty. Your move is almost embarrassing in its simplicity: look at the two people in front, wave the smaller ticket forward, repeat. When one queue runs dry, the other walks over as-is, it's already sorted internally and everyone left in it is bigger than everything you've placed.

That's the entire algorithm. The interesting part is doing it with pointers without dropping anybody.

The problem, dressed up properly

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

LeetCode 21. Note "splicing together the nodes": you rewire the existing people, you don't create new ones.

The naive attempt

Dump both lists into an array, sort, rebuild.

def merge_two_lists(l1, l2):
    vals = []
    for node in (l1, l2):
        while node:
            vals.append(node.val)
            node = node.next
    vals.sort()
    # ...rebuild a fresh list from vals

O((n+m) log(n+m)) for the sort, O(n+m) extra space, and it ignores the gift the problem handed you: both lists are already sorted. Sorting sorted data is paying for groceries you already own.

The weapon: the dummy node

Here's the annoyance the naive version dodged. When you build the merged line node by node, the first attachment is special: there's no line yet, so "attach to the end of the line" has nothing to attach to. You end up writing separate code for "starting the line" and "growing the line", with an if guarding which case fires.

The fix costs one line: create a fake node, the dummy, and let it be the permanent start of the line. Now the line is never empty, the first real node attaches to the dummy like any other node, and the special case evaporates. At the end, the answer is dummy.next.

Think of it as a bakery mannequin standing at the counter holding ticket zero. Nobody serves it, but everyone lines up behind it, and "behind the mannequin" is a place that always exists.

Watching it work

A: 1 → 2 → 4, B: 1 → 3 → 4

step   front of A   front of B   attach       merged line so far
1      1            1            B's 1 (tie→either)   0(dummy) → 1
2      1            3            A's 1        0 → 1 → 1
3      2            3            A's 2        0 → 1 → 1 → 2
4      4            3            B's 3        0 → 1 → 1 → 2 → 3
5      4            4            A's 4        0 → 1 → 1 → 2 → 3 → 4
6      -            4            splice B     0 → 1 → 1 → 2 → 3 → 4 → 4

Step 6 is the free lunch: queue A emptied, so the rest of queue B (just the 4) attaches in a single pointer assignment, no loop needed. Return dummy.next, skipping the mannequin.

The code

def merge_two_lists(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
    dummy = ListNode()
    tail = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    tail.next = l1 if l1 else l2    # splice the survivor
    return dummy.next

Gotchas

1. Forgetting the leftover splice. The while stops when one list empties, not both. Without tail.next = l1 if l1 else l2, everyone still standing in the other queue goes home without pastries. On sorted inputs the survivors are always valid as-is, splice and done.

2. Advancing the wrong pointer. Attach from l1, advance l1. Attaching from one list while stepping the other duplicates one queue and drops the other. Symptom: output is sorted but has wrong members.

3. Building with < instead of <=. Both work for correctness here, but <= keeps the merge stable: ties preserve original order, list1 first. Some problems (and some interviewers) care. Free to do, so do it.

4. Creating new nodes. tail.next = ListNode(l1.val) works but allocates n+m nodes for no reason and violates the "splice the nodes" instruction. Rewire, don't rebuild.

Complexity

Every node is examined and attached exactly once.

Time: O(n + m). Space: O(1). Just the dummy and two walkers.

Boss down. XP gained.

One line, fully sorted, and the croissants move at maximum speed.

What you walked away with:

• The dummy node: a fake head that makes "the line is empty" impossible, killing special cases
• Merge by repeated smaller-front selection, then splice the survivor in O(1)
• <= for stability, and always return dummy.next
• Rewire existing nodes, never rebuild

Keep this merge warm. Boss 10 asks you to do it with k queues at once, and this two-queue version is the inner gear of that machine.

Next up: Boss 3 — The Night Watchman. A museum guard follows glowing arrows from room to room, and some prankster rewired one arrow to point backward. Does the guard's route ever end, or does he walk in circles until sunrise? You can't mark the rooms and you can't carry a notebook. Two runners, one track, and the most famous meeting in computer science.