当前位置: 首页 > news >正文

Leetcode23. 合并k个升序链表

一、题目描述:

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

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

  1. 示例 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. 示例 2:
    • 输入:lists = []
    • 输出:[]
  3. 示例 3:
    • 输入:lists = [[]]
    • 输出:[]
  • 提示:
    • k == lists.length
    • 0≤k≤1040 \leq k \leq 10^40k104
    • 0≤lists[i].length≤5000 \leq lists[i].length \leq 5000lists[i].length500
    • −104≤lists[i][j]≤104-10^4 \leq lists[i][j] \leq 10^4104lists[i][j]104
    • lists[i] 按 升序 排列
    • lists[i].length 的总和不超过 10410^4104

二、解决思路和代码

1. 解决思路

  • 分析:将列表中的链表分别进行两两合并(合并两个升序链表见Leetcode21),直到列表中只有一个链表

2. 代码

    from typing import *class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def merge2Link(self, link1: Optional[ListNode], link2: Optional[ListNode]) -> Optional[ListNode]:cur = head = ListNode(val=-1)while link1 and link2:temp = link1if link1.val<=link2.val:link1 = link1.nextelse:temp = link2link2 = link2.nexttemp.next = cur.nextcur.next = tempcur = tempif link1: cur.next = link1if link2: cur.next = link2return head.nextdef mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:if len(lists)==0: return Nonewhile len(lists)>1:ls = []if len(lists)%2==1: ls.append(lists[-1])for i in range(len(lists)//2):ls.append(self.merge2Link(lists[2*i], lists[2*i+1]))lists = lsreturn lists[0]
http://www.lryc.cn/news/25645.html

相关文章:

  • 从用户出发,互联网产品策划方法论
  • STM32 E18-D80NK红外检测
  • Linux常用命令--进程和计划任务管理
  • Unity TextMeshPro
  • 虹科分享| 浅谈HK-Edgility边缘计算平台
  • React Router v6详解
  • 帮助100w人成功入职的软件测试面试常见问题以及答案
  • tensorflow2.4--2.回归问题分析
  • 【2023】DevOps、SRE、运维开发面试宝典之Kafka相关面试题
  • CentOS系统编译安装PHP-5.6.27版本
  • 和风SDK查询城市ID(保姆级教程)
  • 暴力递归到动态规划
  • Java:Java仍然处于领先地位?
  • 虚拟地址空间
  • Python基础篇(十五)-- Pygame游戏编程
  • LeetCode 热题 HOT 100 Java 题解 -- Part 2
  • 【项目实战】IDEA常用快捷键汇总
  • 更新 TKK 失败,请检查网络连接。谷歌翻译 translation插件不能用解决办法 亲测有效
  • SpringBoot整合MybatisPlus多数据源
  • 【教程】如何使用Java生成PDF文档?
  • I.MX6ULL内核开发13:pinctrl子系统和gpio子系统-led实验
  • Linux系列 使用vi文本编辑器
  • 【java基础】接口(interface)
  • ChatGPT(GPT3.5) OpenAI官方API正式发布
  • CAD中如何将图形对象转换为三维实体?
  • 【K8S笔记】Kubernetes 集群架构与组件介绍
  • 9 怎么登录VNC
  • MPI ubuntu安装,mpicc,mpicxx,mpif90的区别
  • 移动端笔记
  • 操作系统笔记、面试八股(一)—— 进程、线程、协程