Merge k Sorted Lists

The problem

You are given an array lists of k linked lists (k is the length of lists). Each list is sorted from small to large. Merge them all into one sorted linked list and return its head.

Example 1

Input: lists = [[2, 6, 9], [1, 7], [3, 4, 8]]

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

All 8 nodes from the 3 lists, in one sorted chain.

list 0

269

head

list 1

17

head

list 2

348

head

merged

12346789

Example 2

Input: lists = []

Output: []

No lists at all, so the result is empty.

Example 3

Input: lists = [[], [5]]

Output: [5]

Empty lists add nothing.

Constraints

• 0 ≤ k ≤ 10,000
• 0 ≤ length of each list ≤ 500
• −10,000 ≤ Node.val ≤ 10,000
• Each list is sorted from small to large.
• N, the total number of nodes, is at most 10,000.

Clarifying questions

Can k be 0, or a list be empty?

Yes, both. Empty lists simply add nothing.

Should we reuse the nodes?

Yes. Relink the existing nodes. No copies are needed.

Which matters more, k or N?

Both can be 10,000. A good answer must not multiply them together.

Can values repeat?

Yes. Equal values may come out in any order.

Spot the pattern

Like merging two lists, the next node is always one of the current heads, the smallest one. With k heads, finding that smallest one is the real cost. A structure that keeps “the smallest of a changing set” ready is a min-heap: a tree kept so the smallest item is always on top. Pop and push both take about log k steps.

Solutions

Scan all headsO(k·N)Min-heapO(N log k)

Show all

Two other ways work too. Copying every value and sorting costs O(N log N) and copies all the nodes. Merging the lists in pairs, round after round, is also O(N log k), the same as the heap.

Scan all heads O(k·N)

The idea

Do what merging two lists does, but with k lists. At each step, look at the head of every list and pick the smallest. Link it after the tail and move that list forward. Stop when every list is empty.

It is correct, but every step scans all k heads, even though only one of them changed.

Walkthrough

list 0

269

head

list 1

17

head

list 2

348

head

merged

1. dummy = tail = ListNode()
2. while True:
3. best = None
4. for i in range(len(lists)):
5. if lists[i] and (best is None or lists[i].val < lists[best].val):
6. best = i
7. if best is None: break
8. tail.next = lists[best]; tail = tail.next
9. lists[best] = lists[best].next
10. return dummy.next

Each step, look at the head of all 3 lists and take the smallest one.

← BackStep →Play1 / 10

Code

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

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Scan all heads: each step, check the head of every list and take the
    // smallest. N steps of k checks, so O(k * N) time and O(1) memory.
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(), tail = dummy;
        while (true) {
            int best = -1;
            // The next node is the smallest head, so check every head.
            for (int i = 0; i < lists.length; i++) {
                if (lists[i] != null && (best == -1 || lists[i].val < lists[best].val)) best = i;
            }
            // Every list is empty.
            if (best == -1) break;
            tail.next = lists[best];
            tail = tail.next;
            lists[best] = lists[best].next;
        }
        return dummy.next;
    }
}

Big O

Time O(k·N)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines compare one head with the best so far. They sit inside two loops: the outer loop takes one node per run, and the inner loop checks all k heads. One comparison is 1 step.

   1. dummy = tail = ListNode()
   2. while True:
   3. best = None
   4. for i in range(len(lists)):
   5. if lists[i] and (best is None or lists[i].val < lists[best].val):
   6. best = i
   7. if best is None: break
   8. tail.next = lists[best]; tail = tail.next
   9. lists[best] = lists[best].next
   10. return dummy.next

2. 2 Count the runs on Example 1

   Example 1 has k = 3 lists and N = 8 nodes. Each of the 8 steps checks 3 heads. One last scan finds every head empty and stops.

   (8 + 1) × 3 = 27 checks.

   step	1	2	3	4	5	6	7	8	end
   heads checked	3	3	3	3	3	3	3	3	3

   total

   (8 + 1) × 3 = 27

3. 3 Write the count for any n

   The outer loop runs once per node, plus once to stop. Each run checks k heads:

   (N + 1) × k = k·N + k

   Check it with Example 1: 3 × 8 + 3 = 27.

4. 4 Keep only the part that grows fastest

   Drop the + k. It is smaller than k·N whenever there is at least one node. What is left is k·N. With k and N both up to 10,000, that is far too many.

   So the time is O(k·N).

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

   The code keeps dummy, tail, best and i. The nodes are relinked, not copied. The space is O(1).

   dummytailbesti

Min-heap O(N log k)

The idea

Put the head of every list into a min-heap, ordered by value. Then repeat:

1. Pop the smallest node. Link it after the tail.
2. If that node has a next node, push the next node in. It is the new head of that list.

The heap never holds more than one node per list, so at most k nodes. Finding the smallest is free (it is on top), and a pop or a push costs about log₂ k steps.

Why it is correct: the smallest node left is always the head of some list, and every list’s head is in the heap. So the popped node is always the smallest one left.

Walkthrough

list 0

269

head

list 1

17

head

list 2

348

head

merged

min-heap smallest first

1 (list 1)2 (list 0)3 (list 2)

1. heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
2. heapify(heap)
3. dummy = tail = ListNode()
4. while heap:
5. val, i, node = heappop(heap)
6. tail.next = node; tail = node
7. if node.next:
8. heappush(heap, (node.next.val, i, node.next))
9. return dummy.next

Put the head of each list in a min-heap. The heap always holds at most one node per list, so at most 3 nodes.

← BackStep →Play1 / 10

Code

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

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Min-heap: keep one head per list in a heap, so the smallest is always on
    // top. N pops and pushes of log k each: O(N log k) time, O(k) memory.
    public ListNode mergeKLists(ListNode[] lists) {
        java.util.PriorityQueue<ListNode> heap =
            new java.util.PriorityQueue<>((first, second) -> Integer.compare(first.val, second.val));
        for (ListNode node : lists) {
            if (node != null) heap.add(node);
        }
        ListNode dummy = new ListNode(), tail = dummy;
        while (!heap.isEmpty()) {
            ListNode node = heap.poll();
            tail.next = node;
            tail = node;
            // The node after it is the new head of its list, so it joins the heap.
            if (node.next != null) heap.add(node.next);
        }
        return dummy.next;
    }
}

Big O

Time O(N log k)Space O(k)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 pop and at most one push. On a heap with at most k nodes, each of them costs about log₂ k steps. There is one loop.

   1. heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
   2. heapify(heap)
   3. dummy = tail = ListNode()
   4. while heap:
   5. val, i, node = heappop(heap)
   6. tail.next = node; tail = node
   7. if node.next:
   8. heappush(heap, (node.next.val, i, node.next))
   9. return dummy.next

2. 2 Count the runs on Example 1

   Example 1 has N = 8 nodes, so 8 pops. The heap holds at most 3 nodes. The first 5 pops each push the next node of the same list. The last 3 find their list empty, and the heap shrinks.

   8 pushes (3 at the start, 5 later) + 8 pops = 16 heap operations, each on at most 3 nodes.

   	pop 1	pop 2	pop 3	pop 4	pop 5	pop 6	pop 7	pop 8
   heap size	3	3	3	3	3	3	2	1
   push?	yes	yes	yes	yes	yes	no	no	no

3. 3 Write the count for any n

   Every node goes into the heap once and comes out once. Each of those costs about log₂ k steps:

   about 2N × log₂ k

   Check it with Example 1: 2 × 8 = 16 heap operations, each on a heap of at most 3 nodes.

4. 4 Keep only the part that grows fastest

   Drop the 2. What is left is N log k. Compared with k·N, the k became log k. For k = 10,000, that is about 14 instead of 10,000.

   So the time is O(N log k).

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

   The heap holds at most one node per list, so k entries. The space is O(k).

   heap (up to k nodes)dummytail

Common mistake

Pushing nodes the heap cannot compare

In Python, two tuples with the same value fall back to comparing the next field, the node, which crashes. Put the list index in the middle, (val, i, node), so ties are broken by a number. In Java and C#, give the heap a comparator on the value.

Tested at the limits

2,000 random inputs of 0 to 5 lists with 0 to 4 nodes each, with empty lists and many equal values. Scan all heads and the min-heap gave the same merged list every time.

Largest inputs	Result
10,000 lists of one node each (the most lists allowed). Min-heap.	0.006 s, and about 0.8 MB of extra memory: the heap holds one entry per list, which is the O(k) space.
20 lists of 500 nodes, 10,000 nodes in total (the longest lists allowed). Min-heap.	0.002 s, and under 0.001 MB of extra memory: the heap holds only 20 entries.
1,000 lists of one node each. Scan all heads.	0.04 s. At 10,000 lists it would scan 10,000 heads for each of 10,000 nodes, 100 million steps, which is why the heap matters.