继续刷LeetCode 热题 HOT 100 的题目，并且在博客更新我的solutions。在csdn博客中我会尽量用文字解释清楚，相关Java代码大家可以前往我的个人博客jinhuaiyu.com中查看。
今天的题目从两个方向进行解答，其中一种要用到优先队列，作为已经记不太清楚的我，先去学习了一下优先队列……
题目：合并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

solution 1：分治
看到题目，大家很容易想到的一个解题方向是，我们已经在前面解决过两条升序链表的合并，k条是不是可以利用之前的方法。这个时候，分治就体现出来了，如果k条升序链表两两合并，一轮合并以后再两两合并……最后合并到两条的时候再合并一次即得到最终结果。我们如果采用第一条和第二条合并完了，得到的结果再和第三条合并……要合并k次。但如果像二路归并那样，把k条从中间分成两组，就变成了两个子问题，子问题再从中间分成子问题，直到最后只要求两条链表合并。接着子问题再往回得到父问题的解。这其实就是一个简单的递归，只需要logk次合并。分治在这里降低了时间复杂度。

solution 2：优先队列
看到题目时，大家除了会想到利用之前合并两条链的方法来进行两两合并，也会想到能不能像两条链表合并时一样，每次比较k条链表当前第一个结点，然后把最小的放入新链表最后面。直接比较的话，每放一个结点进入新链表就要比较k-1次，一共有kn个结点，整个时间复杂度将是O(k²n)。我们如果想降低时间复杂度，可以从比较入手。使用优先队列来优化比较，优先队列将k个链表当前的头结点放入，会将最小的结点移动到顶部，可以弹出它接到新链表后，然后将这个结点对应的链表的下一个结点放入优先队列。其实优先队列就是一种二叉堆。可以在O(logk)的时间复杂度内得出最小结点。这样一来，总的时间复杂度就降到了O(kn×logk)。
java提供了优先队列的相关类可以直接使用，但是我们要实现它的比较器，即两个结点是通过其value值来比较大小的。实现比较器有很多种方法，包括为要比较的类实现比较接口，直接实现一个比较器类，或者用lambda表达式。这些内容大家可以直接在百度上搜到，我在代码中提供了后两者方法，官方解答中使用了第一种方法。

Finally，带有详细注释的代码放在放在我的个人博客http://jinhuaiyu.com/leetcode-merge-k-sorted-lists/