Merge k Sorted Lists(priority_queue)
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
struct cmp{
//overload
bool operator()(ListNode *a,ListNode *b) const{
return a->val > b->val;
}
};
ListNode *mergeKLists(vector<ListNode *> &lists) {
// write your code here
int len = lists.size();
ListNode *dummy = new ListNode(0),*curr = dummy;
priority_queue<ListNode*,vector<ListNode*>,cmp>pq;
//push all ListNdoe to heap
for(int i=0;i<len;i++){
if(lists[i] != NULL){
pq.push(lists[i]);
}
}
while(!pq.empty()){
curr->next = pq.top();
curr = curr->next;
pq.pop();
if(curr->next){
pq.push(curr->next);
}
}
return dummy->next;
}
};