leetcode 23. Merge k Sorted Lists 合并 K 个升序链表 (困难)

作者：okokabcd

2022 年 8 月 11 日
山东
本文字数：1007 字
阅读完需：约 3 分钟

leetcode 23. Merge k Sorted Lists 合并K个升序链表(困难)

220811_23. Merge k Sorted Lists 合并 K 个升序链表(困难)

一、题目大意

标签: 栈和队列

https://leetcode.cn/problems/merge-k-sorted-lists

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 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

二、解题思路

这里需要将 k 个排序链表融合成一个排序链表，多个输入一个输出，类似于漏斗，因此可以利用最小堆的概念。

取每个 Linked List 的最小节点放入一个 heap 中，排成最小堆，然后取出堆顶最小的元素放入合并的 List 中，然后将该节点在其对应的 List 中的下一个节点插入到 heap 中，循环上面步骤。

三、解题方法

3.1 Java 实现

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {        PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));        for (ListNode node : lists) {            if (node != null) {                pq.add(node);            }        }
        ListNode ret = null;        ListNode cur = null;        while (!pq.isEmpty()) {            ListNode node = pq.poll();            if (ret == null) {                cur = node;                ret = cur;            } else {                cur.next = node;                cur = cur.next;            }            if (node.next != null) {                pq.add(node.next);            }        }        return ret;    }
    /**     * Definition for singly-linked list.     */    public class ListNode {        int val;        ListNode next;
        ListNode() {        }
        ListNode(int val) {            this.val = val;        }
        ListNode(int val, ListNode next) {            this.val = val;            this.next = next;        }    }}

复制代码

四、总结小记

2022/8/11 疫情常态化了

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/f6c83accfd0dd8816df426388】。文章转载请联系作者。

okokabcd

关注

还未添加个人签名 2019.11.15 加入

一年当十年用的Java程序员

发布

暂无评论

创作场景