#23 Merge k Sorted Lists - Solution

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

k == lists.length
0 <= k <= 10⁴
0 <= lists[i].length <= 500
-10⁴ <= lists[i][j] <= 10⁴
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 10⁴.

The #23 Merge k Sorted Lists problem asks you to merge multiple sorted linked lists into a single sorted list. A naive approach would repeatedly scan all list heads to find the smallest element, but this quickly becomes inefficient as the number of lists grows.

A more optimal strategy uses a min-heap (priority queue). By inserting the head node of each list into a heap, you can always extract the smallest element in O(log k) time. After removing the smallest node, the next node from that same list is inserted into the heap. This ensures the merged list remains sorted while efficiently processing all nodes.

Another powerful technique is divide and conquer, similar to merge sort. Pair up lists and merge them recursively until only one sorted list remains. This reduces the total number of comparisons and scales well for large inputs.

Both strategies achieve strong performance and are commonly discussed in coding interviews.

Approach	Time Complexity	Space Complexity
Min Heap (Priority Queue)	O(N log k)	O(k)
Divide and Conquer	O(N log k)	O(log k)

Solutions (4)

Merge Using a Min-Heap

This approach utilizes a min-heap (priority queue) to efficiently merge k sorted linked lists. The heap will help us identify the minimum element among the lists efficiently.

Initial step involves inserting the head of each list into the min-heap.
Then, continuously extract the smallest element from the min-heap and append it to the merged list.
If there’s a next element in the list from which the node was extracted, push that into the min-heap.

This ensures that the smallest elements are appended to the resulting list in sorted order.

Time Complexity: O(N log k), where N is the total number of nodes and k is the number of linked lists. Each insertion and extraction from the heap takes log k time, and there are N nodes in total.
Space Complexity: O(k), due to the heap that at most stores one node from each list.

Python Java

1import heapq
2
3class ListNode:
4    def __init__(self, x):
5        self.val = x
6        self.next = None
7
8    # For min-heap comparison
9    def __lt__(self, other):
10        return self.val < other.val
11
12class Solution:
13    def mergeKLists(self, lists):
14        if not lists or len(lists) == 0:
15            return None
16        heap = []
17        for l in lists:
18            if l:
19                heapq.heappush(heap, l)
20        dummy = ListNode(0)
21        current = dummy
22        while heap:
23            node = heapq.heappop(heap)
24            current.next = node
25            current = current.next
26            if node.next:
27                heapq.heappush(heap, node.next)
28        return dummy.next

Explanation

The Python solution uses the built-in heapq module which provides an efficient priority queue implementation. Each ListNode is wrapped so that it is comparable based on its val, allowing the heap operations to work correctly. The solution maintains a heap of size k, thus ensuring efficient merging.

Divide and Conquer

This approach follows the divide-and-conquer methodology to merge the lists incrementally.

Recursively divide the array of lists into two halves until you have single lists to merge.
Then, merge the two halves by recursively calling and merging further down the line, akin to a merge sort process.

Time Complexity: O(N log k), where N is the total number of nodes and k is the number of lists.
Space Complexity: O(log k) for recursion stack space.

C++JavaScript

1#include <vector>
2using namespace std;
3
4struct ListNode {
5    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        return mergeKLists(lists, 0, lists.size() - 1);
    }
    
private:
    ListNode* mergeKLists(vector<ListNode*>& lists, int left, int right) {
        if (left == right) return lists[left];
        int mid = (right + left) / 2;
        ListNode* l1 = mergeKLists(lists, left, mid);
        ListNode* l2 = mergeKLists(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }
    
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* last = &dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                last->next = l1;
                l1 = l1->next;
            } else {
                last->next = l2;
                l2 = l2->next;
            }
            last = last->next;
        }
        last->next = l1 ? l1 : l2;
        return dummy.next;
    }
};