超详细！图解「合并 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 名同学，请最矮的同学出列”这件事情可以交给优先队列（最小堆、最小索引堆均可）去完成。在连续的两次出队之间完成“穿针引线”的工作。

下面的图解释了上面的思路。

代码实现

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(Nlog⁡k)，这里 N 是这 ? 个链表的结点总数，每一次从一个优先队列中选出一个最小结点的时间复杂度是 O(log⁡k)，故时间复杂度为O(Nlog⁡k)。
• 空间复杂度：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(Nlog⁡k)，这里 N 是这 k 个链表的结点总数，k 个链表二分是对数级别的。
• 空间复杂度：O(1)，合并两个排序链表需要“穿针引线”的指针数是常数个的。