草庐IT

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

okokabcd 2023-03-28 原文

一、题目大意

标签: 栈和队列

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 疫情常态化了
升序leetcodeListNodelists算法与数据结构

有关leetcode 23. Merge k Sorted Lists 合并K个升序链表(困难)的更多相关文章

  1. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

  2. ruby - 按值降序排列散列，然后按升序键入 ruby - 2

    我有这样的哈希trial_hash={"key1"=>1000,"key2"=>34,"key3"=>500,"key4"=>500,"key5"=>500,"key6"=>500}我按值降序排列:my_hash=trial_hash.sort_by{|k,v|v}.reverse我现在是这样理解的:[["key1",1000],["key4",500],["key5",500],["key6",500],["key3",500],["key2",34]]但我希望当值相同时按键的升序排序。我该怎么做？例如:上面的散列将以这种方式排序:[["key1",1000],["key3",500

  3. git使用常见问题（提交代码，合并冲突） - 2

    文章目录git常用命令（简介，详细参数往下看）Git提交代码步骤gitpullgitstatusgitaddgitcommitgitpushgit代码冲突合并问题方法一：放弃本地代码方法二：合并代码常用命令以及详细参数gitadd将文件添加到仓库：gitdiff比较文件异同gitlog查看历史记录gitreset代码回滚版本库相关操作远程仓库相关操作分支相关操作创建分支查看分支：gitbranch合并分支：gitmerge删除分支：gitbranch-ddev查看分支合并图：gitlog–graph–pretty=oneline–abbrev-commit撤消某次提交git用户名密码相关配置g

  4. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  5. ruby - Sort_by Ruby，一个降序，一个升序 - 2

    我已经搜索过这个问题的答案，但没有成功，有一个类似的问题，但答案在这种情况下不起作用，它按数字项目排序。SimilarQuestion-Thatdidnotwork我正在尝试使用ruby​​的sort_by对一个项目进行降序排序和另一个升序排序。我只能找到一个。代码如下:#PrimarysortLastNameDescending,withtiesbrokenbysortingAreaofinterest.people=people.sort_by{|a|[a.last_name,a.area_interest]}任何指导肯定会有所帮助。示例数据:输入罗素，逻辑欧拉，图论伽罗瓦，抽象代

  6. Ruby 哈希直接访问与合并 - 2

    有什么区别:@attr[:field]=new_value和@attr.merge(:field=>new_value) 最佳答案 如果您使用的是merge!而不是merge，则没有区别。唯一的区别是您可以在合并参数中使用多个字段(意思是:另一个散列)。例子:h1={"a"=>100,"b"=>200}h2={"b"=>254,"c"=>300}h3=h1.merge(h2)putsh1#=>{"a"=>100,"b"=>200}putsh3#=>{"a"=>100,"b"=>254,"c"=>300}h1.merge!(h2)pu

  7. ruby - 在两个 ActiveRecord 类之间合并/复制属性的好方法？ - 2

    之前有人问过这个问题，我发现了以下clip关于如何一次设置一个类对象的所有属性，但由于批量分配保护，这在Rails中是不可能的。(例如，您不能Object.attributes={})有没有一种很好的方法可以将一个类的属性合并到另一个类中？object1.attributes=object2.attributes.inject({}){|h,(k,v)|h[k]=vifObjectModel.column_names.include?(k);h}谢谢。 最佳答案 利用assign_attributes使用:without_prote

  8. ruby - 合并 nanoc 中的项目 - 2

    我一直在尝试使用nanoc用于生成静态网站。我需要组织一个复杂的排列页面，我想让我的内容保持干燥。包含或合并的概念在nanoc系统中如何运作？我已阅读文档，但似乎找不到我想要的内容。例如:我如何获取两个部分内容项并将它们合并到一个新的内容项中。在staticmatic您可以在您的页面中执行以下操作。=partial('partials/shared/navigation')类似的约定在nanoc中如何运作？ 最佳答案 这里是nanoc的作者。在nanoc中，部分是布局。因此，您可以拥有layouts/partials/shared/

  9. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  10. ruby-on-rails - Rails 合并两个哈希数组？ - 2

    我很难理解我需要合并两个哈希数组的逻辑，看来我已经问过hisquestionawhileback以不同的方式，我还尝试了其他一些方法，例如此处提供的答案:mergingarraysofhashes任何形式的帮助理解这对我来说都是非常有帮助的。假设我有以下数组，这是方法本身的输出，所以你可以想象那些:timestamp是Time对象[{:timestamp=>2011-12-1900:00:00UTC},{:timestamp=>2011-12-1901:00:00UTC},{:timestamp=>2011-12-1902:00:00UTC},{:timestamp=>2011-12-

随机推荐