p07 Merge Two Sorted Lists — Progressive Hints

Rule: Read ONE hint. Set a 5-minute timer. Try again. Only read the next hint if the timer expires.

Hint 1 — Pattern family

The first node of your output isn’t special — except your code probably treats it that way. There’s a single allocation trick that makes “first append” identical to every other append. Reach for it.

Hint 2 — Data structure / state

You walk both lists simultaneously, always advancing the one whose current value is smaller. You need a way to append to your output without re-finding its end every time. So: keep a pointer to the output’s tail.

Hint 3 — The key insight

Use a dummy (sentinel) node before the real output head. Then tail = dummy initially. Every append is tail.next = chosen; tail = tail.next. No special case for the first node. Return dummy.next (skip the dummy).

When one list is exhausted, the other’s remainder is already sorted. Just point at it. Don’t iterate.

Hint 4 — Pseudocode skeleton

dummy = new ListNode()
tail = dummy
while l1 and l2:
    if l1.val <= l2.val:        # <= for stability
        tail.next = l1
        l1 = l1.next
    else:
        tail.next = l2
        l2 = l2.next
    tail = tail.next
tail.next = l1 if l1 else l2    # leftover tail — O(1) attach
return dummy.next

Two things to check yourself: (a) you wrote <=, not <; (b) the leftover attach is ONE line, not a second while loop.

Hint 5 — Full algorithm

The iterative version is as in Hint 4. Loop invariant: at the top of each iteration, dummy.next ... tail is a sorted list of all consumed nodes, and the remaining l1 and l2 are sorted suffixes whose first elements are ≥ tail.val. When one becomes None, the other’s entire remainder is sorted and ≥ tail, so attaching it preserves the sorted property.

Why dummy node: without it, you’d write if result is None: result = chosen; tail = chosen for the first append, creating a branch in your hot loop. With it, every iteration is identical. This is the “sentinel removes the special case” pattern — it reappears in every list mutation problem.

Recursive variant (Google likes this):

def merge(l1, l2):
    if l1 is None: return l2
    if l2 is None: return l1
    if l1.val <= l2.val:
        l1.next = merge(l1.next, l2); return l1
    l2.next = merge(l1, l2.next); return l2

Elegant but O(N1+N2) stack — risky in Python past N=1000.

Time O(N1+N2). Space O(1) iterative, O(N1+N2) recursive.