Merge Two Sorted Lists (LC 21)

Pattern: Linked List - Dummy Node Technique
Difficulty: Easy
Key Concept: Use a dummy sentinel node to simplify edge case handling when building a new list

1. Problem Statement

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Constraints (typical):

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

---

2. Algorithm (Dummy Node)

Idea: Maintain a tail pointer on a new list. Repeatedly attach the smaller of the two current heads, then advance that list. A dummy node gives a stable “previous” node so the first real attachment does not need special cases.

Pseudocode:

dummy = new ListNode(0)   // value irrelevant
tail = dummy

while list1 != null AND 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

---

3. Beginner Analysis — Dummy Node Pattern

• Without a dummy, the first merge step has no “previous” node yet, so you often write extra branches for “if result head is null…”.
• dummy.next becomes the true head after all links are set; dummy itself is never part of the logical merged list.
• The dummy’s val (e.g. 0) does not matter; only dummy.next is returned.
• In Java, unreachable nodes are garbage-collected; you do not manually free the dummy (unlike C++ where you might delete a heap-allocated dummy if you used new).

---

4. Dry Run — list1 = [1,2,4], list2 = [1,3,4]

Step	Compare	Attach	tail after	Remaining list1	Remaining list2
init	—	—	dummy	1→2→4	1→3→4
1	1 vs 1	list1’s 1	→1	2→4	1→3→4
2	2 vs 1	list2’s 1	→1→1	2→4	3→4
3	2 vs 3	list1’s 2	→1→1→2	4	3→4
4	4 vs 3	list2’s 3	→1→1→2→3	4	4
5	4 vs 4	list1’s 4 (tie, either OK)	→…→4	∅	4
6	—	append rest	→…→4→4	∅	∅

Merged: 1 → 1 → 2 → 3 → 4 → 4.

---

5. Brute Force Java — Collect, Sort, Rebuild

Not optimal, but illustrates an alternative: copy values, sort, build new nodes.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class SolutionBrute {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        List<Integer> values = new ArrayList<>();
        for (ListNode p = list1; p != null; p = p.next) {
            values.add(p.val);
        }
        for (ListNode p = list2; p != null; p = p.next) {
            values.add(p.val);
        }
        Collections.sort(values);
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }
}

---

6. Optimal Java — Iterative (Dummy Node) + Recursive

Iterative:

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) {
                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:

class SolutionRecursive {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

---

7. Java & Language Tricks

Topic	Note
new ListNode(0) as dummy	Sentinel; return dummy.next.
Java GC	No manual free; dummy becomes eligible for GC when unreachable.
No < for nodes	Compare with list1.val and list2.val, not the node references.
C++	If you new a dummy, you must delete it after linking (or use a stack-allocated dummy struct).

---

8. Complexity

Approach	Time	Space
Brute (collect + sort)	O((n+m) log(n+m))	O(n+m)
Iterative merge	O(n+m)	O(1) extra (reusing nodes)
Recursive merge	O(n+m)	O(n+m) call stack worst case

Here n and m are the lengths of the two lists.