力扣题解：23.合并K个升序链表（困难）

前言

这道题是合并两个有序链表的升级版，理论层面的难度并不算大，在编码过程中可能涉及到一些深一些的知识点，本题采用了优先队列，并自定义了比较器实现小顶堆。

该题涉及：

• 优先队列

题目

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i]按升序排列
• lists[i].length的总和不超过10^4

思路：我们思考对两个链表进行合并，有以下过程，我们总是采取两个链表中值较小的一个进行合并操作。

1->3->4    3->4       3->4      3->4       3->4          null
		->         ->        ->         ->            ->
1->1->2    1->1->2    1->2      2          null          null

null    -> 1       -> 1->1   -> 1->1->1 -> 1->1->1->2

-> 1->1->1->2->3->4

对于k个链表，我们当然可以两两合并，但是这样会重复遍历很多元素。能不能一次合并k个链表呢？
我们考虑对于两个链表的合并，我们总是拿值较小的一个进行合并，拓展至k个链表，那就是我们拿值最小的一个进行合并操作。
例如有3个链表的合并，我们总是拿三个链表头节点中值最小的一个进行合并操作。

1->3    3       3       3          null
     ->      ->      ->         ->            -> ...
2->3    2->3    2->3    3          3
     ->      ->      ->         ->            -> ...
1->4    1->4    4       4          4          

null -> 1    -> 1->1 -> 1->1->2 -> 1->1->2->3 -> ...

原理到这部分就结束了，到了编码问题，我们采用优先队列来实现。
priority_queue是优先队列，其队首元素总是最大或最小的，维护其有序性的时间复杂度为O(logn)，采用堆的方式进行排序，这样我们每次都能很快的拿到最小的那个元素。

题解：

• 时间复杂度：O(knlogk)，其中k为链表数，n为某个链表的最大节点数。我们最多会遍历kn个节点，而每次遍历维护有序性的时间复杂度为O(logk)

class Solution {
public:
    struct compare{//自定义比较器
        bool operator()(ListNode* n1, ListNode* n2){
            return n1->val > n2->val;
        }
    };

    //采用自定义比较器，实现小顶堆，因为默认大顶堆
    priority_queue <ListNode*, vector<ListNode*>, compare> q;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto node: lists) {
            if (node != nullptr) 
	            q.push(node);
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto f = q.top(); q.pop();
            tail->next = f;
            tail = tail->next;
            if (f->next != nullptr)
	            q.push(f->next);
        }
        return head.next;
    }
};