Merge Two Sorted Linked Lists Into One

Given the heads of two sorted singly linked lists list1 and list2, merge them into a single sorted list and return its head. The merged list should be made by re-using the nodes of the original two lists — no new node values. Both inputs already arrive sorted, which is exactly the structure the optimal solution leans on: a two-pointer merge walks both lists side by side, always taking whichever current node holds the smaller value, and splices it directly into the result — turning two independent sorted chains into one sorted chain in a single O(n+m) pass with no extra nodes.

Test Case 1:

Input:list1 = [1, 2, 4], list2 = [1, 3, 4]

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

Explanation:Every value from both lists, interleaved so the result stays sorted.

Test Case 2:

Input:list1 = [], list2 = []

Output:[]

Explanation:Two empty lists merge into an empty list.

Test Case 3:

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

Output:[0]

Explanation:One list empty — the result is just the other list.

Constraints

◆0 ≤ number of nodes in list1, list2 ≤ 50 each
◆-100 ≤ node value ≤ 100
◆Both list1 and list2 are sorted in non-decreasing order

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

list1 (sorted values) — 0-6 integerslist2 (sorted values) — 0-6 integers

1	class Solution {
2	public Node mergeTwoSortedLists(Node list1, Node list2) {
3	Node dummy = new Node(0);
4	Node tail = dummy;
5	while (list1 != null && list2 != null) {
6	if (list1.val <= list2.val) {
7	tail.next = list1;
8	list1 = list1.next;
9	} else {
10	tail.next = list2;
11	list2 = list2.next;
12	}
13	tail = tail.next;
14	}
15	tail.next = (list1 != null) ? list1 : list2;
16	return dummy.next;
17	}
18	}
19

Linked List

1

list1

2

4

null

Linked List

1

list2

3

4

null

Linked List

null

Variables

taildummy

INITIALIZE

A dummy node lets the first spliced-in node attach the same way as every later one. tail starts at dummy.

Step 1 / 29

Approach & Solutions

Brute Force — Collect Both Into an Array, Sort, Rebuild

Good

Walk both lists, copying every value into one array. Sort that array from scratch, then build a brand-new list from it. Correct, but it throws away the fact that list1 and list2 were each already sorted — re-sorting everything is unnecessary work, and building all-new nodes costs extra space the optimal solution doesn't need.

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

SpaceO(n+m)

Java

Try it out

// Node definition used in this problem:
// class Node {
//     int val;
//     Node next;
// }

class Solution {
    public Node mergeTwoSortedLists(Node list1, Node list2) {
        List<Integer> vals = new ArrayList<>();
        Node curr = list1;
        while (curr != null) {
            vals.add(curr.val);
            curr = curr.next;
        }
        curr = list2;
        while (curr != null) {
            vals.add(curr.val);
            curr = curr.next;
        }
        Collections.sort(vals);
        Node dummy = new Node(0);
        Node tail = dummy;
        for (int v : vals) {
            tail.next = new Node(v);
            tail = tail.next;
        }
        return dummy.next;
    }
}

Optimal — Two Pointers, Splice Nodes In Place

Optimal

Both lists are already sorted, so there's no need to look at every value twice. Walk list1 and list2 together with two pointers: at each step, whichever current node holds the smaller value gets spliced onto the end of the result, and that list's pointer advances. No new nodes are ever created — existing ones are just re-linked. Once one list runs out, the other's remaining nodes are already sorted, so the whole remainder attaches in one shot.

TimeO(n+m)

SpaceO(1)

Java

Try it out

// Node definition used in this problem:
// class Node {
//     int val;
//     Node next;
// }

class Solution {
    public Node mergeTwoSortedLists(Node list1, Node list2) {
        Node dummy = new Node(0);
        Node 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;
    }
}

Constraints

Try the Dry Run

Approach & Solutions

Brute Force — Collect Both Into an Array, Sort, Rebuild

Optimal — Two Pointers, Splice Nodes In Place

Related Problems