题解 | #合并k个已排序的链表#

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

struct cmp{
    bool operator() (const ListNode* a, const ListNode* b){
    return a->val > b->val;
    }
};

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