Merge Two Sorted Lists

The problem

You are given the heads of two singly linked lists, list1 and list2. Each list is sorted from small to large. Join them into one sorted list by relinking their nodes, and return its head.

Example 1

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

Output: [1, 2, 3, 4, 7, 8, 9]

The nodes of both lists, top and bottom, are linked into one chain in order.

Example 2

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

Output: [5]

One list is empty, so the answer is the other list.

Example 3

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

Output: [2, 2, 2]

Equal values can come in any order.

Constraints

• 0 ≤ n, m ≤ 50, where n and m are the lengths of the two lists
• −100 ≤ Node.val ≤ 100
• Both lists are sorted from small to large.

Clarifying questions

Can a list be empty?

Yes, one or both. If both are empty, return null.

Should we make new nodes?

No need. Reuse the nodes from the two lists and change their next pointers.

Can values repeat?

Yes, inside a list and across lists. Equal values may come out in either order.

Are both lists sorted the same way?

Yes, both from small to large.

Spot the pattern

Two sorted inputs, one sorted output. The smallest value left is always at the front of one of the two lists, so one comparison finds it. That is the merge step of merge sort, done on linked lists with two pointers.

Solutions

Copy and sortO((n + m) log(n + m))SpliceO(n + m)

Show all

This problem has two approaches. A recursive merge does the same work as the splice, but uses a call stack of up to n + m calls.

Copy and sort O((n + m) log(n + m))

The idea

Ignore that the lists are sorted. Copy every value from both lists into one array, sort the array, and build a brand new list from it.

It is correct and easy to get right. But sorting costs more than a single pass, and the work it does was already done: each list was in order.

Walkthrough

list1

147

list2

2389

values

1. values = []
2. for node in (list1, list2):
3. while node:
4. values.append(node.val); node = node.next
5. values.sort()
6. dummy = tail = ListNode()
7. for value in values:
8. tail.next = ListNode(value)
9. tail = tail.next
10. return dummy.next

Pour every value from both lists into one array. Then sort it and build a new list from it.

← BackStep →Play1 / 17

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Copy and sort: pour all values into one array, sort it, build a new list.
    // The sort costs O((n + m) log(n + m)), and the copy costs O(n + m) memory.
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        java.util.List<Integer> values = new java.util.ArrayList<>();
        for (ListNode node : new ListNode[] { list1, list2 }) {
            for (; node != null; node = node.next) values.add(node.val);
        }
        java.util.Collections.sort(values);
        // A dummy head means the first real node needs no special case.
        ListNode dummy = new ListNode(), tail = dummy;
        for (int value : values) {
            tail.next = new ListNode(value);
            tail = tail.next;
        }
        return dummy.next;
    }
}

Big O

Time O((n + m) log(n + m))Space O(n + m)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Three parts repeat. The copy loop handles one node per run. The build loop makes one node per run. Both are 1 step per run. In between, the sort does its own repeated work on the whole array.

   1. values = []
   2. for node in (list1, list2):
   3. while node:
   4. values.append(node.val); node = node.next
   5. values.sort()
   6. dummy = tail = ListNode()
   7. for value in values:
   8. tail.next = ListNode(value)
   9. tail = tail.next
   10. return dummy.next

2. 2 Count the runs on Example 1

   Example 1 has 3 + 4 = 7 values. The copy takes 7 runs and the build takes 7 runs. A good sort on 7 values takes about 7 × log₂ 7, so about 20 steps.

   7 + 20 + 7 = about 34 steps.

   part	copy	sort	build
   steps	7	about 7 × log 7 ≈ 20	7

3. 3 Write the count for any n

   Call the total number of nodes N = n + m. Copying and building visit every value once. Sorting N values takes about N log₂ N steps:

   N + N log₂ N + N = N log₂ N + 2N

   Check it with Example 1: 7 × 2.8 + 14 ≈ 34.

4. 4 Keep only the part that grows fastest

   Drop the 2N. The sort is the biggest part: log₂ N keeps growing, so N log₂ N pulls away from 2N as N grows. What is left is N log N, which is (n + m) log(n + m).

   So the time is O((n + m) log(n + m)).

5. S Space: count the extra memory the same way

   The array holds n + m values, and the new list has n + m new nodes. Both grow with the input, so the space is O(n + m).

   values (n + m values)n + m new nodes

Splice O(n + m)

The idea

Start with a dummy node: a fake node in front of the answer, so the first real node is not a special case. tail is the last node of the merged list so far.

While both lists have nodes, compare their front nodes. Link the smaller one after tail, and move that list forward. When one list runs out, link the whole rest of the other list in one step: it is already sorted, and all its values are at least as big as tail.

Return dummy.next. No node is copied, only the next pointers change.

Why it is correct: both lists are sorted, so the smallest node left is always one of the two front nodes. Taking it each time builds the merged list in order.

Walkthrough

1. dummy = tail = ListNode()
2. while list1 and list2:
3. if list1.val <= list2.val:
4. tail.next, list1 = list1, list1.next
5. else:
6. tail.next, list2 = list2, list2.next
7. tail = tail.next
8. tail.next = list1 or list2
9. return dummy.next

D is a dummy node. tail is the end of the merged list so far. list1 and list2 point at the smallest node each list has left.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Splice: the smallest node left is always at the front of one list.
    // Take it and repeat. One pass, so O(n + m) time and O(1) memory.
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // A dummy head means the first real node needs no special case.
        ListNode dummy = new ListNode(), tail = dummy;
        while (list1 != null && list2 != null) {
            // <= keeps equal values stable, but either choice is correct.
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        // One list is empty. The other is sorted and no smaller than tail, so link all of it.
        tail.next = list1 != null ? list1 : list2;
        return dummy.next;
    }
}

Big O

Time O(n + m)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each run of the loop does one comparison and moves two pointers. That is 1 step. There is one loop. The final link of the rest is a single step.

   1. dummy = tail = ListNode()
   2. while list1 and list2:
   3. if list1.val <= list2.val:
   4. tail.next, list1 = list1, list1.next
   5. else:
   6. tail.next, list2 = list2, list2.next
   7. tail = tail.next
   8. tail.next = list1 or list2
   9. return dummy.next

2. 2 Count the runs on Example 1

   Example 1 has 7 nodes. The loop links 1, 2, 3, 4 and 7. Then list1 is empty and the loop stops. The last two nodes, 8 and 9, come along in one link.

   5 runs + 1 link = 6 steps.

   	run 1	run 2	run 3	run 4	run 5	after
   linked	1	2	3	4	7	8, 9 (one link)

3. 3 Write the count for any n

   Each run takes one node. The loop stops when one list is empty, so in the worst case it takes every node but the last:

   at most n + m − 1 runs, plus 1 link

   Check it with Example 1: at most 3 + 4 − 1 = 6 runs. It took 5, because 8 and 9 were left together.

4. 4 Keep only the part that grows fastest

   Drop the − 1 and the + 1. They do not change how the work grows. What is left is n + m. Both lists can be long, so we keep both letters.

   So the time is O(n + m).

5. S Space: count the extra memory the same way

   The code makes one dummy node and keeps one tail pointer. That is fixed, for any n and m, so the space is O(1).

   dummytail

Common mistake

Forgetting the leftover nodes

When the loop ends, one list may still have nodes. If you stop there, they are lost. One line, tail.next = list1 or list2, links all of them at once.

Tested at the limits

2,000 random pairs of sorted lists, 0 to 5 nodes each, with equal values across the two lists and either list sometimes empty. The copy and sort and the splice gave the same list every time.

Largest inputs	Result
50 nodes in each list (the most allowed), values from the whole range mixed together. Splice.	Under 0.001 s, and under 0.001 MB of extra memory: just one dummy node, because the old nodes are reused.
50 nodes in each list. Copy and sort.	Under 0.001 s, and about 0.01 MB of extra memory: 100 new nodes and a list of the values.