BM5、合并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、遍历链表数组，把每个链表的开头元素都填入到优先队列里面，优先队列会自己处理，把头节点最小的值放到前面去。

2、接下来，开始弹出优先队列的队头元素，它是里面最小的结点，把它连接到最后的结果上面去。

3、每次弹出一个结点来，再把一个新的结点加入到优先队列里面，而这个新的结点就是弹出结点所在链表的下一个结点。

4、反复执行第 3 步操作也就完成了整个排序操作。

三、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {

        // 队列是遵循先进先出（First-In-First-Out）模式的，但有时需要在队列中基于优先级处理对象。
        // PriorityQueue 和队列 Queue 的区别在于 ，它的出队顺序与元素的优先级有关
        // 对 PriorityQueue 调用 remove() 或 poll() 方法 ，返回的总是优先级最高的元素
        // Java 中 PriorityQueue 通过二叉小顶堆实现
        // PriorityQueue 默认是一个【小顶堆】，可以通过传入自定义的 Comparator 函数来实现【大顶堆】
        Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);

        // 遍历所有链表
        for (ListNode node: lists) {
            // PriorityQueue 实现了 Queue 接口，不允许放入 null 元素
            if (node != null) {
                // 把所有链表都加入到优先队列当中
                // 优先队列会自己处理，把头节点最小的值放到前面去
                pq.offer(node);
            }

            // ListNode node = pq.peek();

            // System.out.println(node.val);
        }


        // 添加一个虚拟头节点（哨兵），帮助简化边界情况的判断
        ListNode dummyHead = new ListNode(-1);

        // 合并成功之后的尾节点位置
        ListNode tail = dummyHead;

        // 遍历优先队列，取出最下值出来
        while (!pq.isEmpty()) {

            // 取出优先队列，即二叉堆的头节点，最小的节点
            ListNode minNode = pq.poll();

            // 把这个节点连接到合并链表的尾部
            tail.next = minNode;

            // tail 的位置也随之发生变化
            tail = minNode;

            // PriorityQueue 实现了 Queue 接口，不允许放入 null 元素
            if (minNode.next != null) {
                // 再把新的节点也加入到优先队列当中
                pq.offer(minNode.next);
            }
        }

        // 整个过程其实就是「多路归并」过程
        // 返回结果
        return dummyHead.next;
    }
}

一、题目描述

二、题目解析

三、参考代码

相关文章