23. Merge k Sorted Lists

struct compare {
    bool operator()(const ListNode* l, const ListNode* r) {
        return l->val > r->val;
    }
};
ListNode *mergeKLists(vector<ListNode *> &lists) { //priority_queue
    priority_queue<ListNode *, vector<ListNode *>, compare> q;
    for(auto l : lists) {
        if(l)  q.push(l);
    }
    if(q.empty())  return NULL;

    ListNode* result = q.top();
    q.pop();
    if(result->next) q.push(result->next);
    ListNode* tail = result;            
    while(!q.empty()) {
        tail->next = q.top();
        q.pop();
        tail = tail->next;
        if(tail->next) q.push(tail->next);
    }
    return result;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
struct cmp {
    bool operator () (ListNode *a, ListNode *b) {
        return a->val > b->val;
    }
};
class Solution {
public:

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>,cmp> pq;
        ListNode * dummyNode = new ListNode(0);
        ListNode * cur = dummyNode;
        for(int i = 0; i<lists.size();++i){
            if(lists[i]) pq.push(lists[i]);
        }
        while(!pq.empty()){
            ListNode* temp =pq.top();
            pq.pop();
            cur->next=temp;
            if(temp->next){
                pq.push(temp->next);
            }
            cur=cur->next;
        }
        return dummyNode->next;
    }
};

• https://discuss.leetcode.com/topic/21812/difference-between-priority-queue-and-heap-and-c-implementation