专栏首页weixuqin 的专栏leecode刷题(27)-- 合并k个排序链表

leecode刷题(27)-- 合并k个排序链表

leecode刷题(27)-- 合并k个排序链表

合并k个排序链表

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

示例:

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

思路

以前做过合并两个有序链表的问题,所以刚开始想到的解法与之类似,我们可以先合并两个有序链表,再用合并的新链表去合并第三个链表:

1->1->3->4->4->5
1->1->2->3->4->4->5->6

其实如果我们学习过堆相关的知识,还可以用最小堆来解决这个问题:

  1. 读取所有链表值
  2. 构造一个最小堆(python中有 headp 方法,java中有 PriorityQueue 方法
  3. 根据最小堆构造一个链表

代码如下

python 描述

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

from heapq import heapify, heappop

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        
        # 读取所有节点值
        h = []
        for node in lists:
            while node:
                h.append(node.val)
                node = node.next

        if not h:
            return None
        
        # 构造一个最小堆
        heapify(h)  # 转换为最小堆

        # 构造链表
        root = ListNode(heappop(h))
        curnode = root
        while h:
            nextnode = ListNode(heappop(h))
            curnode.next = nextnode
            curnode = nextnode
        return root

java 描述

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 读取所有节点值
        List<Integer> h = new ArrayList();
        for (ListNode node: lists) {
            while (node != null) {
                h.add(node.val);
                node = node.next;
            }
        }

        // 构造一个最小堆
        if (!h.isEmpty())   return null;
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue();
        // 将元素添加进最小堆中
        for (Integer h1: h) {
            priorityQueue.offer(h1);
        }

        //构造链表
        ListNode root = priorityQueue.poll();
        ListNode curNode = root;
        while (!priorityQueue.isEmpty()) {
            ListNode nextNode = priorityQueue.poll();
            curNode.next = nextNode;
            curNode = nextNode;
        }
        return root;
    }
}

总结

上述 python 的代码能通过提交,但是 java 代码部分我快被类型转换弄晕了,代码不能通过运行,这里只是给出一种思路,日后有时间自己会再完善的,写下来也是当作自己学习记录的一部分,希望看到文章的小伙伴能帮忙指出本人的不足。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leecode刷题(20)-- 删除链表中的节点

    请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。

    希希里之海
  • scrapy 调试功能

    希希里之海
  • scrapy 调试功能

    希希里之海
  • 【剑指offer】从尾到头打印链表

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 剑指Offer的学习笔记(C#篇)-- 从尾到头打印链表

    这个题目搞了一段时间,因为解法好多,比如:是用递归法呢还是循环呢,要不要使用栈呢等等.. 所以,每一种想法都写一下吧,还有一点点的小细节什么的。

    WeiMLing
  • 自开发Web应用和SAP Customer Data Cloud Identity服务的集成

    版权声明:本文为博主汪子熙原创文章,未经博主允许不得转载。 https://jerry.blog....

    Jerry Wang
  • HTML/CSS基础

    子元素的外边距隔着父元素的内边距和边框. 当这两项都不存在的时候, 父子元素垂直外边距相邻, 产生叠加.

    星辉
  • 单细胞高分文献精读系列(1)--近两年文献纵横

    回顾近两年的生物技术热点,单细胞分析技术无疑是各个研究领域大佬们力捧的宠儿。从去年到现在,影响因子20分以上、以单细胞分析为主体的文章已发表近100篇(文末识别...

    用户6317549
  • Golang Leetcode 876. Middle of the Linked List.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/arti...

    anakinsun
  • 微信公众号开发之成为开发者模式

    本文将学习到: 1、如何开发调试微信公众号 2、如何开启开发者模式 3、可能遇到的问题 4、weixin_guide如何成为开发者模式源码解读

    Javen

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动