Leetcode二十三题:合并K个升序链表【22/1000 python】

“合并K个升序链表”,这是一道中等难度的题目,经常出现在编程面试中。以下是该问题的详细描述、解题步骤、不同算法的比较、代码示例及其分析。

问题描述

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

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

示例:

输入: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

方法一:直接合并

解题步骤

  1. 初始化:
    • 如果链表数组为空,则返回None。
    • 如果链表数组中只有一个链表,则直接返回这个链表。
  2. 逐对合并链表:
    • 初始化merged_list为lists[0],即从第一个链表开始。
    • 逐个遍历余下的链表,与merged_list进行合并,每次合并后更新merged_list。
  3. 合并两个链表的函数:
    • 创建一个哑结点dummy作为合并链表的起始节点。
    • 使用两个指针分别指向两个链表的头部,比较指针所指节点的值,将较小值节点连接到结果链表上,然后移动该指针到下一个节点。
    • 如果某一链表遍历完毕,将另一链表的剩余部分直接连接到结果链表的尾部。
    • 返回哑结点的下一个节点,即合并后链表的头部。
  4. 完成合并:
    • 继续遍历并合并剩余的链表,直至所有链表均合并完成。

代码示例

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:dummy = ListNode(0)current = dummywhile l1 and l2:if l1.val < l2.val:current.next = l1l1 = l1.nextelse:current.next = l2l2 = l2.nextcurrent = current.next# Attach the remaining part of l1 or l2current.next = l1 if l1 is not None else l2return dummy.nextdef mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:if not lists:return Noneif len(lists) == 1:return lists[0]merged_list = lists[0]for i in range(1, len(lists)):merged_list = mergeTwoLists(merged_list, lists[i])return merged_list

性能分析

时间复杂度:对于k个链表的情况,直接合并的时间复杂度是O(kN),其中N是链表中的节点总数。这是因为每次合并操作需要遍历涉及的两个链表的长度,而链表长度随着合并次数增加而增长。
空间复杂度:O(1),不计入输入和输出占用的空间,合并过程中只使用了常数额外空间。

结论

直接合并是一个简单直观的方法,适合链表数量较少或对时间复杂度要求不是非常严格的情况。然而,对于大量链表的合并,使用最小堆或分治法(如两两合并)可能会更高效。

方法二:使用最小堆

解题步骤

  1. 初始化最小堆
    • 创建一个空的最小堆(优先队列)来存储链表节点,堆中的元素按节点的值排序。
    • 遍历所有链表,将每个链表的头节点加入最小堆中。
  2. 构建结果链表
    • 创建一个哑结点(dummy node)作为结果链表的头部,这样可以方便地添加新节点。
    • 使用一个指针current跟踪结果链表的最后一个节点。
  3. 遍历并合并
    • 当最小堆不为空时,执行以下操作:
    • 从堆中弹出最小元素(当前最小节点)。
    • 将current的next指针指向这个最小节点。
    • 移动current指针到最小节点。
    • 如果这个最小节点有后继节点,则将后继节点加入最小堆中。
  4. 完成合并
    • 当最小堆为空时,所有链表的节点都已链接到结果链表中。
    • 返回哑结点的next,即合并后链表的头部。

代码示例

import heapqclass ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef mergeKLists(lists):if not lists:return None# Create a heap and a dummy node to start the merged listheap = []dummy = ListNode(0)current = dummy# Initial population of the heap with the first node of each list, if availablefor i, node in enumerate(lists):if node:heapq.heappush(heap, (node.val, i, node))# Iterate over the heap and build the merged listwhile heap:val, idx, node = heapq.heappop(heap)current.next = nodecurrent = current.nextif node.next:heapq.heappush(heap, (node.next.val, idx, node.next))return dummy.next

性能分析

时间复杂度:每个节点被处理一次,而且每次处理涉及的时间复杂度为O(log k),因此总的时间复杂度是O(Nlogk),其中是所有链表中元素的总数,是链表的数量。
空间复杂度:最小堆中最多存储个元素,因此空间复杂度是O(k)。

结论

使用最小堆的方法在合并多个链表时非常有效,尤其是当链表数量较多时。这种方法的时间复杂度相对较低,是因为它能快速地找到当前最小的节点并将其加入到结果链表中,而空间复杂度则主要由堆的大小决定。这使得最小堆方法在处理大规模数据时表现出色。

方法三:分治合并

解题步骤

  1. 递归分治函数定义
    • 创建一个函数mergeKLists,如果列表为空或长度为1,直接返回。
    • 如果列表长度大于1,将链表列表分成两半,分别对这两半递归调用mergeKLists。
  2. 合并两个链表的函数
    • 创建另一个辅助函数mergeTwoLists用于合并两个链表。这个函数将两个链表头作为输入,合并后返回新链表的头。
  3. 执行分治合并
    • 在mergeKLists中,通过递归地将链表数组拆分至只剩单个链表,然后开始合并。
    • 使用mergeTwoLists逐对合并链表,直至整个数组合并为一个链表。
  4. 返回结果
    • 递归完全执行完毕后,返回合并后的链表头部。

代码示例

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:if not l1 or not l2:return l1 or l2dummy = ListNode(0)current = dummywhile l1 and l2:if l1.val < l2.val:current.next = l1l1 = l1.nextelse:current.next = l2l2 = l2.nextcurrent = current.nextcurrent.next = l1 or l2return dummy.nextdef mergeKLists(lists: List[ListNode]) -> ListNode:if not lists:return Noneif len(lists) == 1:return lists[0]mid = len(lists) // 2left = mergeKLists(lists[:mid])right = mergeKLists(lists[mid:])return mergeTwoLists(left, right)

性能分析

时间复杂度
• 每次合并操作需要线性时间,即O(n),其中n是参与合并的两个链表的总节点数。
• 通过每次递归减半链表数组的长度,整体上每层递归需要O(N)时间,其中N是所有链表中元素的总数。
• 递归的深度是O(log k),因此总的时间复杂度是O(N logk)。
空间复杂度
• 递归调用栈的深度为O(logk),因此空间复杂度为O(logk)。

结论

分治合并是解决合并多个链表的问题中非常有效的方法,尤其适合处理大量链表的情况。它的时间复杂度与使用最小堆的方法相同,但通常在实际应用中由于常数因子较小而表现更优。此外,分治法的代码结构清晰,易于理解和实现,使其成为面试和实际工程中的常用策略。

总结

在这里插入图片描述
合并 K 个升序链表可以通过多种算法实现,包括直接合并、使用最小堆和分治合并。在面试中,根据具体情况选择最适合的方法。其中,使用最小堆和分治合并的方法因其较优的时间复杂度通常更受青睐。这些方法不仅展示了数据结构的有效使用,也体现了分治策略在实际问题中的应用。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/308988.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

如何在Photoshop中,使用本地Stable Diffusion WebUI的绘图能力

&#x1f3c3;‍♂️文章背景 相信设计师朋友们最熟悉的软件应该就是photoshop了&#xff0c;现在AI绘图虽然控制性越来越强&#xff0c;但跟ps比起来&#xff0c;还是要弱很多&#xff0c;尤其是图层、蒙版、笔刷、色调校色等等功能&#xff0c;所以就算是使用SD或者midjourn…

数据分析案例(三):基于RFM分析的客户分群

实验2 基于RFM分析的客户分群 Tips&#xff1a;"分享是快乐的源泉&#x1f4a7;&#xff0c;在我的博客里&#xff0c;不仅有知识的海洋&#x1f30a;&#xff0c;还有满满的正能量加持&#x1f4aa;&#xff0c;快来和我一起分享这份快乐吧&#x1f60a;&#xff01; 喜欢…

RabbitMQ-死信队列常见用法

目录 一、什么是死信 二、什么是死信队列 ​编辑 三、第一种情景&#xff1a;消息被拒绝时 四、第二种场景&#xff1a;. 消费者发生异常&#xff0c;超过重试次数 。 其实spring框架调用的就是 basicNack 五、第三种场景&#xff1a; 消息的Expiration 过期时长或队列TTL…

【Linux】序列化与反序列化{服客编程/守护进程/JSON}

文章目录 1.引入2. 静态成员函数3.TCP&#xff1a;传输控制协议4.守护进程4.0前台进程4.1介绍4.2认识4.3会话4.3ps axj4.4理解4.5/dev/null4.6守护进程和孤儿进程 5.JSON6.完整代码6.1Makefile6.2Socket.hpp6.3Protocol.hpp6.4Log.hpp6.5Daemon.hpp6.6TcpServer.hpp6.7Client.c…

【3GPP】【核心网】核心网/蜂窝网络重点知识面试题二(超详细)

1. 欢迎大家订阅和关注&#xff0c;3GPP通信协议精讲&#xff08;2G/3G/4G/5G/IMS&#xff09;知识点&#xff0c;专栏会持续更新中.....敬请期待&#xff01; 目录 1. 对于主要的LTE核心网接口&#xff0c;给出运行在该接口上数据的协议栈&#xff0c;并给出协议特征 2. 通常…

C++11 设计模式2. 简单工厂模式

简单工厂&#xff08;Simple Factory&#xff09;模式 我们从实际例子出发&#xff0c;来看在什么情况下&#xff0c;应用简单工厂模式。 还是以一个游戏举例 //策划&#xff1a;亡灵类怪物&#xff0c;元素类怪物&#xff0c;机械类怪物&#xff1a;都有生命值&#xff0…

内网渗透-Windows内网渗透

内网渗透-Windows内网渗透 文章目录 内网渗透-Windows内网渗透前言一、信息收集 1.1、SPN1.2、端口连接1.3、配置文件1.4、用户信息1.6、会话收集1.7、凭据收集 navicat&#xff1a;SecureCRT&#xff1a;Xshell&#xff1a;WinSCP&#xff1a;VNC: 1.8、DPAPI1.9、域信任1.10、…

3d怎么按路径制作模型---模大狮模型网

在3D建模中&#xff0c;按路径制作模型是一种常见的技术&#xff0c;特别适用于创建曲线、管道、绳索等线性形状的物体。虽然这项技术可能对初学者来说有些复杂&#xff0c;但通过一步步的指导和实践&#xff0c;你将能够掌握它。本文将详细介绍按路径制作模型的步骤&#xff0…

深拷贝总结

JSON.parse(JSON.stringify(obj)) 这行代码的运行过程&#xff0c;就是利用 JSON.stringify 将js对象序列化&#xff08;JSON字符串&#xff09;&#xff0c;再使用JSON.parse来反序列化&#xff08;还原&#xff09;js对象&#xff1b;序列化的作用是存储和传输。&#xff08…

认识OpenEuler操作系统

引言 在信息技术日新月异的时代&#xff0c;开源软件已成驱动创新的核心动能&#xff0c;其中&#xff0c;OpenEuler作为一款冉冉升起的开源操作系统典范&#xff0c;凭借其对开源精神的坚守与技术创新的不懈追求&#xff0c;自亮相以来便引发了全球关注。本文将全方位深挖Open…

一站式开源持续测试平台 MerterSphere 之测试跟踪操作详解

一、MeterSphere平台介绍 MeterSphere是一站式的开源持续测试平台&#xff0c;遵循 GPL v3 开源许可协议&#xff0c;涵盖测试跟踪、接口测试、UI 测试和性能测试等功能&#xff0c;全面兼容JMeter、Selenium 等主流开源标准&#xff0c;有效助力开发和测试团队充分利用云弹性…

一分钟学会旋转一个矩阵

&#x1f60e; 作者介绍&#xff1a;我是程序员行者孙&#xff0c;一个热爱分享技术的制能工人。计算机本硕&#xff0c;人工制能研究生。公众号&#xff1a;AI Sun&#xff0c;视频号&#xff1a;AI-行者Sun &#x1f388; 本文专栏&#xff1a;本文收录于《深入浅出算法》系列…

荔枝派LicheePi 4A RISCV板子支持的好玩的AI模型

荔枝派LicheePi 4A 是基于 Lichee Module 4A 核心板的 高性能 RISC-V Linux 开发板&#xff0c;以 TH1520 为主控核心&#xff08;4xC9101.85G&#xff0c; RV64GCV&#xff0c;4TOPSint8 NPU&#xff0c; 50GFLOP GPU&#xff09;&#xff0c;板载最大 16GB 64bit LPDDR4X&…

【Linux】账号和权限管理

目录 一、用户账号与组账号 二、添加用户账号-useradd 三、修改用户账号的属性-usermod 四、更改用户命令-passwd 五、删除用户账号-userdel 六、添加组账号-groupadd 七、添加删除组成员-gpasswd 八、删除组账号-groupdel 九、查询账号信息-groups、id、finger、w、w…

Ubuntu-22.04安装KVM虚拟机并安装Windows10

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、KVM是什么&#xff1f;二、安装步骤1.检查虚拟化2.查看KVM虚拟化3.安装KVM4.启用后台进程5.添加用户组6.重启电脑 三、使用步骤1.添加虚拟机2.配置虚拟机3.…

直播弹幕系统设计

本文仅提供思路参考&#xff0c;并非完备的详细设计。 特点 其实很类似IM即时通讯系统&#xff0c;是个变种&#xff0c;本质也是在一个空间内收发消息 消息及时性强&#xff0c;过期消息意义不大用户松散&#xff0c;随时来随时走可能有瞬时大批量弹幕&#xff08;比如比赛精…

GET与POST:详述HTTP两大请求方法的语义、数据处理机制、安全特性与适用场景

GET和POST方法在HTTP请求中具有明确的角色分工和特性差异。GET适用于读取操作和不敏感数据的传递&#xff0c;强调可缓存性和安全性&#xff0c;而POST适用于写入操作和敏感数据的提交&#xff0c;提供了更大的数据承载能力和更强的隐私保护。本文详细介绍了GET与POST请求方法的…

XTTS数据迁移

文章目录 一、全量迁移1、源端和目标端都需要配置XTTS脚本&#xff08;源库和目标库都需要进行下列配置&#xff09;2、源端调用 xttdriver.pl -p做迁移准备3、将源端的数据文件副本和rmanconvert.cmd传到目标端4、在目标端对数据文件拷贝进行字节序的转换 二、XTTS 第1~n次增量…

Web前端 Javascript笔记3

1、垃圾回收机制 内存中的生命周期 1、内存分配 2、内存使用&#xff08;读写&#xff09; 3、内存回收&#xff0c;使用完毕之后&#xff0c;垃圾回收器完成 内存泄漏&#xff1a;该回收的&#xff0c;由于某些未知因素&#xff0c;未释放&#xff0c;叫做内存泄漏 栈&#xf…

【DNS】

文章目录 DNS域名解析系统&#xff08;Domain Name System&#xff09;DNS系统需要解决的问题DNS域名解析系统&#xff08;Domain Name System&#xff09;问题1&#xff1a;DNS名字空间(The DNS Name Space&#xff09;DNS名字空间(The DNS Name Space)DNS名字空间(The DNS Na…