☕ DSA Java Articles

Topics › Linked List › Medium Problems of LL

Merge two Sorted Lists

Hard TUF ID 613 SDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the heads of two singly linked lists, a and b, each sorted in non-decreasing order. Merge them into a single list that is also sorted in non-decreasing order and return its head. The intended solution splices together the existing nodes rather than allocating new ones.

Constraints: each list has between 0 and 50 nodes in the LeetCode version, values fit in an int. Either list, or both, may be empty.

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

Example 1

a = 1 -> 2 -> 4
b = 1 -> 3 -> 4
answer = 1 -> 1 -> 2 -> 3 -> 4 -> 4      // every node from both lists, in order

Example 2

a = (empty)
b = 0
answer = 0                               // merging with an empty list returns the other list

Example 3

a = (empty), b = (empty)
answer = (empty)

Approach 1: Brute force, collect and sort

Intuition. Forget for a moment that the inputs are sorted. The output is simply “all the values, in sorted order”, so you could pour every value into one container, sort it, and build a brand-new list from the result. It is correct by construction and easy to write. Its weakness is that it throws away the most valuable fact in the problem: both inputs are already sorted, which is exactly the information a merge needs to avoid sorting from scratch.

Algorithm.

  1. Walk a and b, appending every value to an ArrayList.
  2. Sort the list.
  3. Build a new linked list from the sorted values behind a dummy node and return dummy.next.
static ListNode bruteForce(ListNode a, ListNode b) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode t = a; t != null; t = t.next) vals.add(t.val);
    for (ListNode t = b; t != null; t = t.next) vals.add(t.val);
    Collections.sort(vals);
    ListNode dummy = new ListNode(0), tail = dummy;
    for (int v : vals) {
        tail.next = new ListNode(v);
        tail = tail.next;
    }
    return dummy.next;
}

Complexity. Time O((m + n) log(m + n)) for the sort, where m and n are the lengths. Space O(m + n) for the value list and the new nodes. It also violates the “splice the existing nodes” requirement, since the original nodes are discarded.

Approach 2: Recursion

Intuition. Look at the two heads. The smallest value in the entire answer must be one of them, because each head is the smallest value of its own list. So the answer starts with the smaller head. What comes after it? Exactly the merge of everything that remains: the rest of the list you took from, and the whole of the other list. That is the same problem on a smaller input, which is a natural fit for recursion.

The base cases are the empty lists. Merging anything with an empty list gives back the non-empty one unchanged, and since that list is already sorted no work is needed.

Correctness follows by induction on m + n. If either list is empty the base case is correct. Otherwise, assume the recursive call correctly merges the smaller input. The chosen head is no larger than every remaining value (it is at most the other head, and each head is at most the rest of its own list), so placing it in front of a correctly merged remainder gives a correctly sorted whole.

Algorithm.

  1. If a is empty return b; if b is empty return a.
  2. If a.val <= b.val, set a.next to the merge of a.next and b, and return a.
  3. Otherwise set b.next to the merge of a and b.next, and return b.
static ListNode recursive(ListNode a, ListNode b) {
    if (a == null) return b;
    if (b == null) return a;
    if (a.val <= b.val) {
        a.next = recursive(a.next, b);
        return a;
    }
    b.next = recursive(a, b.next);
    return b;
}

Complexity. Time O(m + n): each call places one node and does constant work. Space O(m + n) for the call stack, one frame per node placed.

The stack is the real cost. With lists of tens of thousands of nodes the default Java thread stack can overflow, so the recursive version is elegant to explain but risky in production. It is still worth knowing, because the same “choose the smaller head, recurse on the rest” thinking underlies the iterative version and merge sort.

Approach 3: Optimal, iterative splice with a dummy node

Intuition. Make the same decision as the recursion, but build the answer from front to back with a tail pointer instead of from back to front on the call stack. At every step, compare the two current heads, hook the smaller node onto tail, advance that list, and advance tail. No new nodes are created; you only change next pointers.

Two details make the code short and safe:

Using <= when the values are equal takes the node from a first. That makes the merge stable, which matters when the nodes carry extra data and merge sort must preserve the original order of equal keys.

Algorithm.

  1. Create dummy and set tail = dummy.
  2. While both a and b are non-empty:
    • If a.val <= b.val, attach a and move a forward; otherwise attach b and move b forward.
    • Move tail to the node just attached.
  3. Attach whichever list is still non-empty to tail.next.
  4. Return dummy.next.
static ListNode optimal(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) {                    // <= keeps equal values from a first (stable)
            tail.next = a;
            a = a.next;
        } else {
            tail.next = b;
            b = b.next;
        }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;             // one list is used up: attach the other as it is
    return dummy.next;
}

Dry run on a = 1 -> 2 -> 4, b = 1 -> 3 -> 4:

step head of a head of b take merged so far
1 1 1 a (1 ≤ 1) 1
2 2 1 b 1 1
3 2 3 a 1 1 2
4 4 3 b 1 1 2 3
5 4 4 a (4 ≤ 4) 1 1 2 3 4
end empty 4 attach rest of b 1 1 2 3 4 4

Complexity. Time O(m + n): each loop iteration places one node, and the final attach is constant time. Space O(1) extra: only dummy, tail and the two moving heads. The Java tests confirm that the result is made of exactly the original node objects.

Edge cases and pitfalls