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

**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; } };

Advertisements