23. 合并K个升序链表

题目链接

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目描述

题目分析

1. 使用优先队列

• 找到k个节点中最小值
  二插队节点上浮和下沉 时间复杂度o(logn)，优先队列入队和出队的时间复杂度o(logn)。
  最小堆存放的值：当前每个链表没有被合并的元素的最前面一个。将每个链表第一个值放入一个最小堆，就可以获得k个节点中的最小值点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Cmp{
public:
    bool operator()(const ListNode* a, const ListNode* b){
        return a->val > b->val;
    }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        priority_queue<ListNode*, vector<ListNode*>, Cmp> pq;
        for(auto head : lists){//注意 这里用的auto 
            if(head) pq.push(head);//注意 空值的情况
        }
        while(!pq.empty()){
            ListNode* temp = pq.top();
            cur->next = temp;
            pq.pop();
            cur = temp;//注意这一步
            if(cur->next != nullptr) pq.push(temp->next);
        }
        return dummy->next;
    }
};