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

Problem link

**Solution**

- using a priority queue to keep the organize the k current candidates
- note that the default priority_queue in cpp is max_heap, I need to implement my own comparator function that supports min_heap with pointers as elements

struct compNode {
bool operator()(ListNode *p, ListNode *q) const {
return p->val>q->val;
}
};
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
priority_queue<ListNode*, vector<ListNode*>, compNode> q;
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
ListNode* min_node;
for (auto n:lists){
if (n){
q.push(n);
}
}
while (!q.empty()){
min_node = q.top();
q.pop();
cur -> next = min_node;
cur = cur->next;
min_node = min_node->next;
if (min_node) q.push(min_node);
}
cur -> next = NULL;
cur = dummy->next;
delete (dummy);
return cur;
}
};

### Like this:

Like Loading...

*Related*