超详细！图解「合并 K 个排序链表」
作者 | 李威
来源 | 五分钟学算法
今天分享的题目来源于 LeetCode 第 23 号问题：合并 K 个排序链表。本文采取两种思路进行分析。
题目描述
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
题目解析
方法一：贪心算法、优先队列
思路分析：
1、由于是 ? 个排序链表，那么这 ? 个排序的链表头结点中 val 最小的结点就是合并以后的链表中最小的结点；
2、最小结点所在的链表的头结点就要更新了，更新成最小结点的下一个结点（如果有的话），此时还是这 ? 个链表，这 ?k 个排序的链表头结点中 val 最小的结点就是合并以后的链表中第 2 小的结点。
写到这里，我想你应该差不多明白了，我们每一次都从这 ? 个排序的链表头结点中拿出 val 最小的结点“穿针引线”成新的链表，这个链表就是题目要求的“合并后的排序链表”。
“局部最优，全局就最优”，这不就是贪心算法的思想吗。
这里我们举生活中的例子来理解这个思路。
假设你是一名体育老师，有 3 个班的学生，他们已经按照身高从矮到高排好成了 3 列纵队，现在要把这 3 个班的学生也按照身高从矮到高排列 1 列纵队。我们可以这么做： 1、让 3 个班的学生按列站在你的面前，这时你能看到站在队首的学生的全身； 2、每一次队首的 3 名同学，请最矮的同学出列到“队伍 4”（即我们最终认为排好序的队列），出列的这一列的后面的所有同学都向前走一步（其实走不走都行，只要你能比较出站在你面前的 3 位在队首的同学同学的高矮即可）； 3、重复第 2 步，直到 3 个班的同学全部出列完毕。
具体实现的时候，“每一次队首的 3 名同学，请最矮的同学出列”这件事情可以交给优先队列（最小堆、最小索引堆均可）去完成。在连续的两次出队之间完成“穿针引线”的工作。
下面的图解释了上面的思路。
LeetCode 第 23 题：合并K个排序链表-1
LeetCode 第 23 题：合并K个排序链表-2
LeetCode 第 23 题：合并K个排序链表-3
代码实现
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int len = lists.length;
if (len == 0) {
return null;
}
PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(len, Comparator.comparingInt(a -> a.val));
ListNode dummyNode = new ListNode(-1);
ListNode curNode = dummyNode;
for (ListNode list : lists) {
if (list != null) {
// 这一步很关键，不能也没有必要将空对象添加到优先队列中
priorityQueue.add(list);
}
}
while (!priorityQueue.isEmpty()) {
// 优先队列非空才能出队
ListNode node = priorityQueue.poll();
// 当前节点的 next 指针指向出队元素
curNode.next = node;
// 当前指针向前移动一个元素，指向了刚刚出队的那个元素
curNode = curNode.next;
if (curNode.next != null) {
// 只有非空节点才能加入到优先队列中
priorityQueue.add(curNode.next);
}
}
return dummyNode.next;
}
}
复杂度分析
- 时间复杂度：O(Nlogk)，这里 N 是这 ? 个链表的结点总数，每一次从一个优先队列中选出一个最小结点的时间复杂度是 O(logk)，故时间复杂度为O(Nlogk)。
- 空间复杂度：O(k)，使用优先队列需要 k 个空间，“穿针引线”需要常数个空间，因此空间复杂度为 O(k)。
方法二：分治法
如果我们不想“穿针引线”，那么“递归”、“分治”是一个不错的选择。
代码结构和“归并排序”可以说是同出一辙：
1、先一分为二，分别“递归地”解决了与原问题同结构，但规模更小的两个子问题；
2、再考虑如何合并，这个合并的过程也是一个递归方法。
代码实现
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int len = lists.length;
if (len == 0) {
return null;
}
return mergeKLists(lists, 0, len - 1);
}
public ListNode mergeKLists(ListNode[] lists, int l, int r) {
// 思考这里为什么取等于？这是因为根据下文对 mergeKLists 的递归调用情况，区间最窄的时候，只可能是左右端点重合
if (l == r) {
return lists[l];
}
int mid = (r - l) / 2 + l;
ListNode l1 = mergeKLists(lists, l, mid);
ListNode l2 = mergeKLists(lists, mid + 1, r);
return mergeTwoSortedListNode(l1, l2);
}
private ListNode mergeTwoSortedListNode(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val < l2.val) {
l1.next = mergeTwoSortedListNode(l1.next, l2);
return l1;
}
l2.next = mergeTwoSortedListNode(l1, l2.next);
return l2;
}
}
复杂度分析
- 时间复杂度：O(Nlogk)，这里 N 是这 k 个链表的结点总数，k 个链表二分是对数级别的。
- 空间复杂度：O(1)，合并两个排序链表需要“穿针引线”的指针数是常数个的。