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

1.用最小堆解决这个问题会更好。
2.注意从小到大用大于号。
3.最后只需要循环的放入后续元素即可。

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


public:

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

    ListNode *mergeKLists(vector<ListNode *> &lists) {
       //最小堆
       if(!lists.size()) return NULL;

        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;


        //最小堆
        priority_queue<ListNode*, vector<ListNode*>,cmp> pq;

        for(ListNode* head:lists){
            if(head){
                pq.push(head);
            }
        }

        while(!pq.empty()){
            ListNode* node = pq.top();
            pq.pop();

            if(node->next){
                pq.push(node->next);
            }

            p->next = node;
            p = p->next;

        }

        return dummy->next;

    }
};