21. Merge Two Sorted Lists

Walk both lists in parallel and at each step splice the smaller of the two heads onto the result. A dummy node sitting before the real start of the result list lets us always say tail.next = X without a special case for the very first node.

Why a dummy head?

Without a dummy, the first iteration has to ask: is the result empty? If yes, the chosen node becomes the new head and we have to remember it; if no, we splice it onto the existing tail. Two code paths.

A dummy ListNode(0) sits before the real result. Now there's always something to splice onto, every iteration looks identical, and at the end we return dummy.next.

Steps

1. Create dummy = tail = ListNode(0).
2. While both l1 and l2 are non-None:
   • Pick the smaller head: if l1.val <= l2.val, splice l1; else splice l2.
   • tail.next = chosen, then advance the chosen pointer (l1 = l1.next or l2 = l2.next), then tail = tail.next.
3. After the loop, at most one list is non-empty. Append whichever still has nodes: tail.next = l1 or l2.
4. Return dummy.next.

Walk-through

l1 = 1 → 2 → 4, l2 = 1 → 3 → 4.

Return dummy.next = 1 → 1 → 2 → 3 → 4 → 4. ✓

The <= vs < choice

We compare with <= so that ties go to l1. This preserves stability — when two equal values come from different lists, the one from l1 appears first. Whether you choose < or <= doesn't change correctness, only stability.

Edge cases

• Either list empty: the while skips immediately; the tail-append picks up whichever remains.
• Both empty: the result is just dummy.next = None.
• No new allocation needed: we splice existing nodes; we never call ListNode(...) (except for the dummy).

Complexity

• Time: O(n + m) — every node is visited once.
• Space: O(1) — only the dummy and a few pointers.

import java.util.*;

class Solution {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int v) { val = v; }
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        tail.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}