leetcode23合并K个链表(高频题)

浅浅的花香味﹌ 2023-05-31 07:48 27阅读 0赞

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:  
\[  
1->4->5,  
1->3->4,  
2->6  
\]  
输出: 1->1->2->3->4->4->5->6

一个较为合适的方法，即最小堆来做。  
先存在lists.length个数的最小堆，每次取最小的元素出来，再链上新的链表。

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode mergeKLists(ListNode[] lists) {
        
            
            if(lists == null || lists.length == 0)
                return null;
            Queue<ListNode> queue=new PriorityQueue(lists.length,new Comparator<ListNode>(){
        
    
                    @Override
                    public int compare(ListNode o1,ListNode o2)
                    {
        
                        return o1.val-o2.val;
                    }
    
            });
    
            for(int i = 0;i<lists.length;i++)
            {
        
                if(lists[i]==null)continue;
                queue.add(lists[i]);
            }
    
            ListNode emp = new ListNode(-1);
            ListNode cur = emp;
            while(!queue.isEmpty())
            {
        
                ListNode node = queue.poll();
                cur.next = node;
                cur = node;
                if(node.next!=null)
                {
        
                    queue.add(node.next);
                }
            }
    
            return emp.next;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，27人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 23. 合并K个排序链表（C++）

p.s python版——>[leetcode 23：合并 k 个排序链表][leetcode 23_ k] 题目合并 k 个排序链表，返回合并后的排序链表。请分析和

た入场券/ 2023年07月13日 03:28/ 0 赞/ 3 阅读

相关 leetcode23 合并K个排序链表

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nk

分手后的思念是犯贱/ 2023年06月19日 06:49/ 0 赞/ 20 阅读

相关 leetcode 23 合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例: 输入: \[ 1->4->5, 1->3->4, 2->6 \] 输

迈不过友情╰/ 2023年06月18日 08:53/ 0 赞/ 1 阅读

相关 leetcode23合并K个链表(高频题)

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例: 输入: \[ 1->4->5, 1->3->4, 2->6 \] 输

浅浅的花香味﹌/ 2023年05月31日 07:48/ 0 赞/ 28 阅读

相关 LeetCode 23. 合并K个升序链表 JAVA

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。示例 1：输入：lists = [[1,

灰太狼/ 2022年12月09日 11:34/ 0 赞/ 182 阅读

相关 LeetCode 23. 合并K个升序链表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

红太狼/ 2022年10月28日 10:06/ 0 赞/ 230 阅读

相关 leetcode23合并K个升序链表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

叁歲伎倆/ 2022年10月06日 09:54/ 0 赞/ 256 阅读

相关 LeetCode-23.合并K个排序链表

题目合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例: > 输入: \[ 1->4->5, 1->3->4, 2->6 \] >

╰+攻爆jí腚メ/ 2022年01月26日 13:05/ 0 赞/ 240 阅读

相关 23. 合并K个排序链表

> 知乎ID: 码蹄疾 > 码蹄疾，毕业于哈尔滨工业大学。 > 小米广告第三代广告引擎的设计者、开发者； > 负责小米应用商店、日历、开屏广告业务线研发；

痛定思痛。/ 2021年12月17日 08:53/ 0 赞/ 242 阅读

相关 leetcode【23】合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例: 输入: [ 1->4->5, 1->3->4,

偏执的太偏执、/ 2021年10月03日 01:42/ 0 赞/ 349 阅读