36.Merge Two Sorted Lists

EasyBlind 75Linked List · 2/11

Problem

You are given the heads of two linked lists, list1 and list2, each sorted in non-decreasing order.

Merge them into one sorted list by splicing together the existing nodes (no new value nodes needed) and return the head of the merged list.

Examples

Input:  list1 = [1, 2, 4], list2 = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]
Explanation: Repeatedly take the smaller front node from the two lists.

Input:  list1 = [], list2 = []
Output: []

Input:  list1 = [], list2 = [0]
Output: [0]
Explanation: If one list is empty, the answer is simply the other list.

Constraints

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.

💡 Key Insight

Because both lists are already sorted, the smallest remaining element is always at the front of one of the two lists. Compare the two fronts, attach the smaller one, and advance that list — the same "merge" step used in merge sort. A dummy head node removes all special-casing for the first node.

Brute Force (Collect and Sort)

TimeO((n + m) log(n + m))SpaceO(n + m)

Intuition

Ignore the fact that the inputs are sorted: dump every node into a list, sort by value, and relink them in order.

Algorithm

Walk both lists and add every node to an ArrayList.
Sort the nodes by val.
Link nodes[i].next = nodes[i + 1], and set the last node's next to null.
Return nodes[0] (or null if there are no nodes).

Visualization

list1: 1 -> 2 -> 4      list2: 1 -> 3 -> 4
collected: [1, 2, 4, 1, 3, 4]
sorted:    [1, 1, 2, 3, 4, 4]
relinked:  1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null

Code

java

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

/**
 * Definition for singly-linked list.
 * public 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 Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        List<ListNode> nodes = new ArrayList<>();
        for (ListNode n = list1; n != null; n = n.next) nodes.add(n);
        for (ListNode n = list2; n != null; n = n.next) nodes.add(n);
        if (nodes.isEmpty()) {
            return null;
        }
        nodes.sort((a, b) -> Integer.compare(a.val, b.val));
        for (int i = 0; i + 1 < nodes.size(); i++) {
            nodes.get(i).next = nodes.get(i + 1);
        }
        nodes.get(nodes.size() - 1).next = null; // terminate the merged list
        return nodes.get(0);
    }
}

Complexity

Time: O((n + m) log(n + m)) — sorting all nodes.
Space: O(n + m) — the auxiliary list of nodes.

Recursion

TimeO(n + m)SpaceO(n + m)

Intuition

The merged list starts with the smaller of the two heads. Whatever follows it is just the merge of the remaining nodes — the same problem on smaller input.

Algorithm

If list1 is null, return list2; if list2 is null, return list1.
If list1.val <= list2.val: set list1.next = mergeTwoLists(list1.next, list2) and return list1.
Otherwise set list2.next = mergeTwoLists(list1, list2.next) and return list2.

Visualization

merge([1,2,4], [1,3,4]) -> 1(a) + merge([2,4], [1,3,4])
merge([2,4],   [1,3,4]) -> 1(b) + merge([2,4], [3,4])
merge([2,4],   [3,4])   -> 2    + merge([4], [3,4])
merge([4],     [3,4])   -> 3    + merge([4], [4])
merge([4],     [4])     -> 4(a) + merge([], [4]) -> [4]

Code

java

/**
 * Definition for singly-linked list.
 * public 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 Solution {
    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); // list1 wins this position
            return list1;
        }
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

Complexity

Time: O(n + m) — one call per node placed.
Space: O(n + m) — recursion depth can reach the total number of nodes.

Iterative with Dummy HeadOptimal

TimeO(n + m)SpaceO(1)

Intuition

Keep a tail pointer to the end of the merged list. At each step, attach the smaller front node to tail and advance. When one list runs out, the rest of the other list is already sorted, so attach it in one step. A dummy node in front means tail always exists and the answer is dummy.next.

Algorithm

Create dummy; set tail = dummy.
While both lists are non-null:
- If list1.val <= list2.val, attach list1 and advance list1; otherwise attach list2 and advance list2.
- Advance tail.
Attach whichever list is non-null: tail.next = (list1 != null) ? list1 : list2.
Return dummy.next.

Dry Run

flowchart TD
    A["list1 = 1,2,4<br/>list2 = 1,3,4<br/>merged: dummy"] -->|"1 <= 1: take list1"| B["merged: 1"]
    B -->|"2 > 1: take list2"| C["merged: 1,1"]
    C -->|"2 <= 3: take list1"| D["merged: 1,1,2"]
    D -->|"4 > 3: take list2"| E["merged: 1,1,2,3"]
    E -->|"4 <= 4: take list1"| F["merged: 1,1,2,3,4<br/>list1 empty"]
    F -->|"attach rest of list2"| G["merged: 1,1,2,3,4,4<br/>return dummy.next"]

Code

java

/**
 * Definition for singly-linked list.
 * public 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 Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0); // placeholder before the real head
        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;
        }
        // At most one list still has nodes, and they are already sorted
        tail.next = (list1 != null) ? list1 : list2;
        return dummy.next;
    }
}

Complexity

Time: O(n + m) — each node is attached exactly once.
Space: O(1) — only pointers; existing nodes are reused.

Complexity Comparison

Approach	Time	Space
Collect and Sort	O((n+m) log(n+m))	O(n+m)
Recursion	O(n+m)	O(n+m)
Iterative with Dummy Head	O(n+m)	O(1)

Common Pitfalls

Forgetting to attach the leftover list after the loop — you would drop the tail of one input.
Forgetting to advance tail after attaching a node, so every node overwrites the same tail.next.
Returning dummy instead of dummy.next, which adds a bogus 0 at the front.
Not handling empty inputs; with a dummy head, two null lists naturally return null.
Using < versus <= does not affect correctness here, but <= keeps the merge stable (equal values from list1 come first).