合并K个排序链表

男娘i 2022-01-20 04:07 178阅读 0赞

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

示例:

输入:
    [
      1->4->5,
      1->3->4,
      2->6
    ]
    输出: 1->1->2->3->4->4->5->6
    复制代码

/**
     * 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.length == 0 ){
                return null;
            }
             PriorityQueue< ListNode > min = new PriorityQueue<>(lists.length ,new Comparator<ListNode>(){
               @Override
               public int compare( ListNode o1 , ListNode o2 ){
                   return o1.val - o2.val;
               }
           });
           for( ListNode list : lists ){
               if( list != null )
               min.offer( list );
           }
           ListNode dummy =  new ListNode(-1);
           ListNode cur = dummy; 
           while( min.size() != 0 ){
               ListNode node = min.poll();
               cur.next = node;
               cur = node;
               if( node.next != null )
               min.offer( node.next );
           } 
           return dummy.next; 
        }
    }
    复制代码

解题思路： 用大小为数组长度的最小堆来处理， 先把所有链表放进堆中 ，然后每次弹出堆顶元素 ， 如果弹出元素还有下一个结点 ， 则继续放进堆中。 时间复杂度： 假设链表平均长度为n , 数组个数为k ， 则需要取n\*k个元素， 更新堆需要logk， 则总时间为nklogk.

发表评论取消回复

表情：

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

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

相关阅读

相关合并k个升序链表

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

喜欢ヅ旅行/ 2022年12月18日 02:53/ 0 赞/ 161 阅读

相关 [Leetcode][python]Merge k Sorted Lists/合并K个排序链表

题目大意将k个排序好的链表合并成新的有序链表解题思路堆和分治法代码最小堆方法用一个大小为K的最小堆（用优先队列+自定义降序实现）(优先队

àì夳堔傛蜴生んèń/ 2022年06月09日 09:57/ 0 赞/ 177 阅读

相关 LeetCode 23.Merge k Sorted Lists (合并K个排序链表)

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

Myth丶恋晨/ 2022年05月11日 00:50/ 0 赞/ 199 阅读

相关合并 k 个排序链表

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

傷城~/ 2022年04月22日 11:46/ 0 赞/ 138 阅读

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

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

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

相关合并K个排序链表

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

男娘i/ 2022年01月20日 04:07/ 0 赞/ 179 阅读

相关合并K个排序链表

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

雨点打透心脏的1/2处/ 2022年01月14日 23:35/ 0 赞/ 194 阅读

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

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

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

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

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

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

相关合并K个排序链表

合并K个排序链表题目描述 ![5057999-3fd09622a0f9a1f2.png][] 基本思路这道题属于双链表合并的进阶。理解这道题首先需要了解

清疚/ 2021年10月01日 11:26/ 0 赞/ 266 阅读