## Description

https://leetcode.com/problems/merge-k-sorted-lists/

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6

## Naive solution

We can use a `vector`

to collect all the nodes, and sort according to the values, then iterator the vector to construct a new `LinkList`

.

Time complexity: \(O(NlogN)\), where N is the number of all `ListNode`

. Space complexity: \((N)\).

```
bool compare_node(ListNode* a, ListNode* b) {
return a->val < b->val;
}
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
vector<ListNode*> vec;
for(size_t i = 0; i < lists.size(); i++) {
ListNode* p = lists[i];
while(p) {
vec.push_back(p);
p = p->next;
}
}
sort(vec.begin(), vec.end(), compare_node);
ListNode res(0);
ListNode* p = &res;
for(size_t i = 0; i < vec.size(); i++) {
vec[i]->next = NULL;
p->next = vec[i];
p = vec[i];
}
return res.next;
}
};
```

## Optimization with a priority queue

Another naive solution is also obvious, we can use `K`

pointers to track the current pointer of each `LinkList`

, iterate these pointers to find the minimum pointer in each round, extend the selected node to result.

Can we do better on time performance?

The answer is yes, we can use a priority queue to track the pointers. So that we don’t need to iterate `K`

pointers in each round, instead we fetch the top node from the priority queue.

Time complexity: $O(NlogK) where `N`

is the sum number of nodes, and `K`

is the `lists.size`

. This will be much better than the previous solution because `K`

is smaller than `N`

in most cases.

Space complexity: \(O(N)\) and extra \((k)\) for priority queue.

```
struct cmp {
bool operator() (ListNode* a, ListNode* b) {
return a->val > b->val;
}
};
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
vector<ListNode*> vec = lists;
ListNode res(0);
ListNode* p = &res;
priority_queue<ListNode*, vector<ListNode*>, cmp> Q;
for(int i=0; i<lists.size(); i++) {
if(lists[i] != NULL)
Q.push(lists[i]);
}
while(!Q.empty()) {
ListNode* t = Q.top();
Q.pop();
if(t->next)
Q.push(t->next);
t->next = NULL;
p->next = t;
p = t;
}
return res.next;
}
};
```