Merge Two Sorted Lists

EasyLinked List · Recursion🧩 Recursion & Divide and Conquer LeetCode #21 ↗Updated Oct 30, 2026

Problem

You are given the heads of two singly linked lists, each already sorted in non-decreasing order. Combine them into one sorted list by re-linking the existing nodes, and return the head of the merged list.

Input[1,2,4], [1,3,4]Output[1,1,2,3,4,4]

Input[], []Output[]

Input[], [0]Output[0]

0 ≤ nodes per list ≤ 50 · -100 ≤ Node.val ≤ 100 · both lists sorted non-decreasing

Try it yourself

Java

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The smallest remaining node is always one of the two heads. Repeatedly take the smaller head and append it; when one list runs out, the other's remainder is already sorted and can be attached in one step.

PatternRecursion & Divide and Conquer

Instinct If the answer for n items can be built from the same problem on halves (or smaller pieces) plus a cheap combine step - split, recurse, merge.

Memory hack Split it, trust it, stitch it - nail the base case, take the leap of faith on smaller calls, then glue their answers together.

Open the Recursion & Divide and Conquer guide →

Approaches

Brute ForceCollect, Sort, Rebuild

Time O((n+m) log(n+m))Space O(n+m)

Ignore the sortedness: dump every value from both lists into one array, sort it, and build a fresh list from the sorted values.

Java

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode c = list1; c != null; c = c.next) vals.add(c.val);
    for (ListNode c = list2; c != null; c = c.next) vals.add(c.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;
}

Works for any input, but wastes the given order and allocates new nodes.

BetterRecursive Merge

Time O(n+m)Space O(n+m) stack

If either list is empty, return the other. Otherwise the smaller head is the merged head, and its next is the merge of everything that remains — a direct recursive definition.

Java

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;
}

Linear and elegant, but one stack frame per node.

OptimalIterative Merge with Dummy Head

Time O(n+m)Space O(1)

A dummy node removes the “which list gives the head?” special case. tail marks the end of the merged part; attach the smaller head to it and advance. Finally hook up whichever list is left.

Java

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0), 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; // attach leftover
    return dummy.next;
}

Dry runlist1=[1,2,4] | list2=[1,3,4]

a list1b list2 changed

1
1
a
2

4

|

1
b
3

4

1≤1 take a → 1
2
1

2
a
4

|

1
b
3

4

2>1 take b → 1,1
3
1

2
a
4

|

1

3
b
4

2≤3 take a → ..,2
4
1

2

4
a
|

1

3
b
4

4>3 take b → ..,3
5
1

2

4
a
|

1

3

4
b
4≤4 take a → ..,4
6
1

2

4

|

1

3

4
b
a=null, attach b ✔

Single pass, constant extra space, reuses nodes — the expected answer.

Pro tip

Using <= takes from list1 on ties, which keeps the merge stable — the same step used inside merge sort.

At a glance

Level	Approach	Time	Space
Brute Force	Collect, Sort, Rebuild	`O((n+m) log(n+m))`	`O(n+m)`
Better	Recursive Merge	`O(n+m)`	`O(n+m) stack`
Optimal	Iterative Merge with Dummy Head	`O(n+m)`	`O(1)`

Common pitfalls

Returning dummy instead of dummy.next.
Looping until both lists are null node-by-node instead of attaching the leftover once.
Forgetting to advance tail — every node overwrites the same link.

Interview tips

Introduce the dummy head early; it simplifies many list problems.
Offer the recursive version too, and note its O(n+m) call stack.
Test aloud with one or both lists empty.

Pattern

Two-pointer merge (dummy head) → combine sorted sequences, the core step of merge sort and k-way merge.

My notes saved in this browser