Merge Two Sorted Lists (LC 21)

Pattern: Two-Pointer Merge with Dummy Head Difficulty: Easy Key Concept: Walk both lists with one pointer each. Repeatedly append the smaller head to the result. Use a dummy node so we never special-case the very first append.

Problem Statement

You are given the heads of two sorted singly-linked lists, list1 and list2. Splice them together into one sorted list by rearranging the existing nodes (no copies). Return the head of the merged list.

Example

• list1 = 1 → 2 → 4, list2 = 1 → 3 → 4 → 1 → 1 → 2 → 3 → 4 → 4

---

1. Algorithm & Pseudocode

dummy = new ListNode()
tail = dummy
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 != null) ? list1 : list2
return dummy.next

---

2. Step-by-Step Analysis

Why a dummy head Without it, every append needs an if (result == null) result = node else tail.next = node branch. A dummy lets the loop body be uniform.

Why “smaller (or equal) goes first” Using <= preserves stability — if both heads have the same value, taking from list1 first keeps original order among equals.

Why one final append handles the remainder At loop exit, exactly one list is empty. The non-empty one is already sorted and strictly ≥ anything we’ve appended so far, so we can attach its entire remaining chain at once.

ASCII Trace for list1 = 1→2→4, list2 = 1→3→4

dummy → ?
tail = dummy

step 1: 1 <= 1 → take from list1   dummy → 1(→2→4)         tail=1
step 2: 2 > 1  → take from list2   dummy → 1 → 1(→3→4)     tail=1(second)
step 3: 2 <= 3 → take from list1   dummy → 1 → 1 → 2(→4)   tail=2
step 4: 4 > 3  → take from list2   dummy → 1 → 1 → 2 → 3(→4) tail=3
step 5: 4 <= 4 → take from list1   dummy → 1 → 1 → 2 → 3 → 4 tail=4
list1 exhausted → attach list2 remainder (4)
result:  1 → 1 → 2 → 3 → 4 → 4

---

3. The Dry Run

Step	list1 head	list2 head	Pick	tail value (after)
1	1	1	list1	1
2	2	1	list2	1
3	2	3	list1	2
4	4	3	list2	3
5	4	4	list1	4
6	null	4	attach	4

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

---

4. Java Solution

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

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }

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

Recursive Alternative

class Solution {
    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null) return b;
        if (b == null) return a;
        if (a.val <= b.val) { a.next = mergeTwoLists(a.next, b); return a; }
        else                { b.next = mergeTwoLists(a, b.next); return b; }
    }
}

Iterative — Time: (O(m + n)) Space: (O(1)) Recursive — Time: (O(m + n)) Space: (O(m + n)) call stack

---

5. The “Java vs. Others” Edge

• Reusing existing nodes (no allocation) is required by the problem.
• The recursive version is elegant but can stack-overflow when both lists are very long (~10^4 nodes).
• This routine is reused as the merge step in LC 23 Merge K Sorted Lists (divide-and-conquer).

---

6. Complexity Summary

Approach	Time	Space	Notes
Iterative	O(m + n)	O(1)	Cleanest standard answer
Recursive	O(m + n)	O(m + n)	Beware stack depth