LeetCode 21 – Merge Two Sorted Lists

Merge Two Sorted Lists is the merge step of merge sort, isolated and asked on its own. It is worth writing carefully rather than quickly, because it is a building block: Merge k Sorted Lists calls it, sorting a linked list calls it, and an interviewer who asks one of those will expect this to appear without fuss.

The problem

Given the heads of two sorted linked lists, splice them into one sorted list and return its head. The result should reuse the existing nodes, not copy them.

Input:  1 -> 2 -> 4
        1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4

Input:  (empty), (empty)   Output: (empty)
Input:  (empty), 0         Output: 0

The idea

Keep a pointer into each list. Whichever head is smaller gets appended to the result, and that list advances. Repeat until one list runs out.

Then — and this is the part people over-engineer — attach the remaining list in a single step. Whatever is left is already sorted and already larger than everything emitted so far, so there is no reason to keep looping node by node. One pointer assignment finishes the job:

tail.next = (list1 != null) ? list1 : list2;

If both are null the expression yields null, which is exactly the right terminator. That single line replaces two trailing while loops and the bug where you write if (list1 != null) ... if (list2 != null) ... and the second if quietly overwrites the first.

As in Add Two Numbers, a dummy head removes the "is this the first node?" branch. Build onto dummy, return dummy.next.

Why <= and not <

When the two heads are equal, taking from list1 keeps the merge stable — equal elements come out in the order their lists were given. It changes nothing about whether the output is sorted, so the tests will not catch it either way. It matters the moment the nodes carry a payload beyond the sort key, which is every real use of a merge, and noticing it unprompted is a genuinely good signal.

Java

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

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

        // One list is exhausted; the other is already sorted and larger. Splice it on.
        tail.next = (list1 != null) ? list1 : list2;

        return dummy.next;
    }
}

Python

class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        dummy = tail = ListNode(0)

        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

        tail.next = list1 or list2      # whichever still has nodes, else None

        return dummy.next

list1 or list2 is the direct translation of the ternary: it yields list1 when it is a non-empty node, otherwise list2, and None when both are exhausted.

Complexity

O(m + n) time, and O(1) space. The constant space is the point worth saying out loud: nothing is allocated per node because the existing nodes are relinked, not copied. The only allocation in the whole method is the one dummy.

The recursive formulation is elegant — list1.next = merge(list1.next, list2) — and it costs O(m + n) stack, which on a long list is a stack overflow rather than a style preference. Mention it, write the loop.

What the interviewer is checking

• That you splice the remainder in one assignment rather than looping it out.
• That either list being empty works with no special case — including both.
• That you use a dummy head instead of branching on the first node.
• That you relink rather than allocating new nodes, and can say the space is O(1) because of it.
• Whether you notice <= versus < and can explain why it matters.