21. Merge Two Sorted Lists

Merging two sorted lists is the linked-list version of the merge step in merge sort, and it’s the problem that teaches the single most useful pointer trick in the whole linked list pattern: the dummy head. Get comfortable with it here and the harder list problems stop being about null checks.

The problem

You’re handed the heads of two linked lists that are each already sorted in non-decreasing order. Weave them into one sorted list by relinking the existing nodes — not by copying values — and return the head of the result. (Full statement on LeetCode.)

So 1 -> 3 -> 5 and 2 -> 4 should come back as 1 -> 2 -> 3 -> 4 -> 5, reusing all five original nodes.

Intuition: a dummy head kills the edge cases

The merge itself is obvious — at every step, whichever list has the smaller head node goes next, and you advance that list. Because both inputs are already sorted, comparing just the two front nodes is enough; you never look further ahead.

The annoying part is the first node. Without a placeholder you’d need a branch to decide which head starts the result, then special-case the moment either list runs dry. The fix is a throwaway dummy node that sits in front of the answer. You always append to dummy.next, so there’s no “is this the first node?” question, and at the end you return dummy.next — the real head. That one extra node turns a fiddly problem into a straight loop.

There’s a second detail that makes this clean: when one list empties, the other is already a sorted suffix. You don’t merge it node by node — you point curr.next at whatever remains and you’re done in $O(1)$.

Solution

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0); // placeholder before the real head
        ListNode curr = dummy;            // tail of the list we're building

        while (list1 != null && list2 != null) {
            // <= keeps the merge stable when values tie
            if (list1.val <= list2.val) {
                curr.next = list1;
                list1 = list1.next;
            } else {
                curr.next = list2;
                list2 = list2.next;
            }
            curr = curr.next;
        }

        // one list is empty; the other is a ready-made sorted tail
        curr.next = (list1 != null) ? list1 : list2;
        return dummy.next;
    }
}

Nothing here allocates a new node per element — every curr.next = ... just repoints an existing node, so the whole merge runs in constant extra space. If both inputs are empty, the loop never runs and dummy.next is still null, which is exactly the right answer.

Complexity

	Time	Space
Dummy-node splice	$O(n + m)$	$O(1)$

Each node from either list is visited and relinked once, so time is linear in the combined length $n + m$. Space stays constant because we reuse the input nodes instead of building a copy.

In an interview

Draw the dummy node before you write a line — say “I’ll anchor the result with a placeholder so I never special-case the head.” That framing signals you’ve seen the pattern, and it’s what keeps the code short. The trap most people hit is forgetting the final curr.next = (list1 != null) ? list1 : list2: if you stop at the loop, you silently drop the tail of the longer list. Mention that the <= (rather than <) preserves the relative order of equal values, which is the “stable merge” property.

If asked to scale up, this function is the building block for Merge k Sorted Lists — you either fold it across all lists or feed heads through a heap. And the same careful-pointer-rewiring discipline drives Reverse Linked List; both live in the linked list pattern hub.

References

• LeetCode 21 — Merge Two Sorted Lists