Merge k Sorted Lists

heap • linked-list • divide-and-conquer
Hard
O(nlogk)O(n log k)

Merge k sorted linked lists and return it as one sorted list.

Examples

Input
[[1,4,5],[1,3,4],[2,6]]
Output
[1,1,2,3,4,4,5,6]
Merged list ordered.

Solution

Use a min-heap (priority queue) seeded with the head of each list.
Pop the smallest node, append to result, and if that node has next, push next into heap.
Time: O(nlogk)O(n log k) where n is total nodes and k is number of lists. Space: O(k)O(k) for the heap.

Code Solution

merge-k-lists.cpp
cpp
1
#include <vector>
2
#include <queue>
3
using namespace std;
4


5
struct ListNode { int val; ListNode* next; ListNode(int x): val(x), next(nullptr) {} };
6


7
struct Cmp { bool operator()(ListNode* a, ListNode* b) const { return a->val > b->val; } };
8


9
ListNode* mergeKLists(vector<ListNode*>& lists) {
10
  priority_queue<ListNode*, vector<ListNode*>, Cmp> pq;
11
  for (auto node : lists) if (node) pq.push(node);
12
  ListNode dummy(0), *p = &dummy;
13
  while (!pq.empty()) {
14
    auto cur = pq.top(); pq.pop();
15
    p->next = cur; p = p->next;
16
    if (cur->next) pq.push(cur->next);
17
  }
18
  return dummy.next;
19
}