点击蓝色“五分钟学算法”关注我哟

加个“星标”,天天中午 12:15,一起学算法

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

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

超详细!图解「合并 K 个排序链表」

LeetCode 第 23 题:合并K个排序链表-1

超详细!图解「合并 K 个排序链表」

LeetCode 第 23 题:合并K个排序链表-2

超详细!图解「合并 K 个排序链表」

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(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),合并两个排序链表需要“穿针引线”的指针数是常数个的。
———————–
公众号:五分钟学算法(ID:CXYxiaowu
博客:www.cxyxiaowu.com
知乎:程序员吴师兄
一个正在学习算法的人,致力于将算法讲清楚!
长按下图二维码关注,和你一起领悟算法的魅力

超详细!图解「合并 K 个排序链表」

原文始发于微信公众号(五分钟学算法):超详细!图解「合并 K 个排序链表」