/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
struct myComparor
{
bool operator()(ListNode *lhs, ListNode *rhs) const
{
return lhs->val > rhs->val;
}
};
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
priority_queue<ListNode *, vector<ListNode *>, myComparor > minHeap;
for(ListNode *node : lists) {
if (node)
minHeap.push(node);
}
ListNode dummy(0);
ListNode *p = &dummy;
while(minHeap.size() > 0) {
p->next = minHeap.top();
minHeap.pop();
p = p->next;
if (p->next)
minHeap.push(p->next);
// p->next = NULL; // this line was not necessary
}
return dummy.next;
}
};
Online Judge Solutions
- Google (1)
- LeetCode Solutions (32)
- LintCode Solutions (68)
- Marked (38)
- Misc. (8)
Thursday, December 25, 2014
Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment