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

合并K个升序链表(最优解)

题目来源

23. 合并 K 个升序链表 - 力扣(LeetCode)


题目描述

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

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

示例 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:

输入:lists = []
输出:[]

示例 3:

输入:lists = [[]]
输出:[]

提示:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] 按 升序 排列
  • lists[i].length 的总和不超过 10^4

题目限制

用最优解做出来


思路分析

在解决给定多个按升序排列的链表,将它们合并为一个升序链表的问题时,一种常见思路是采用顺序合并。先实现一个能合并两个有序链表的函数,通过比较节点值大小依次连接节点来合并。在合并多个链表的主函数里,先处理边界情况,如链表数组为空或元素全为空链表时直接返回相应结果,若有有效链表,则先取第一个链表作为初始合并结果,随后从第二个链表起循环调用合并两链表的函数,不断更新合并结果,直至处理完所有链表,最终返回合并好的链表头节点,其时间复杂度为 O(kn)( k为链表个数, n为平均链表长度),空间复杂度为 O(1)。


具体代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTWOLists(ListNode* a,ListNode* b) {ListNode *xt=new ListNode(-1);ListNode *tail=xt;while(a&&b){if(a->val<b->val){tail->next=a;a=a->next;}else{tail->next=b;b=b->next;}tail=tail->next;}if(a)tail->next=a;else tail->next=b;return xt->next;}ListNode* mergeKLists(vector<ListNode*>& lists) {if(lists.empty())return nullptr;ListNode *res=lists[0];for(int i=1;i<lists.size();i++){if(lists[i])res=mergeTWOLists(res,lists[i]);}return res;}
};

这段代码中,Solution类里的mergeTwoLists函数用于合并两个有序链表,通过创建虚拟头节点,利用循环比较两链表当前节点值大小并按需连接,循环结束后处理剩余节点,最终返回合并后链表头节点;mergeKLists函数则是处理多个有序链表的合并,先判断链表数组是否为空,非空时取首个链表为初始结果,再循环调用mergeTwoLists函数依次合并剩余链表,最后返回合并好的完整有序链表的头节点,整体实现了将多个升序链表合并为一个升序链表的功能。

相关文章:

合并K个升序链表(最优解)

题目来源 23. 合并 K 个升序链表 - 力扣&#xff08;LeetCode&#xff09; 题目描述 给你一个链表数组&#xff0c;每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中&#xff0c;返回合并后的链表。 示例 1&#xff1a; 输入&#xff1a;lists [[1,4,5],[1,3,…...

kubernates实战

使用k8s来部署tomcat 1、创建一个部署&#xff0c;并指定镜像地址 kubectl create deployment tomcat6 --imagetomcat:6.0.53-jre82、查看部署pod状态 kubectl get pods # 获取default名称空间下的pods kubectl get pods --all-namespaces # 获取所有名称空间下的pods kubect…...

How to run Flutter on an Embedded Device

basysKom GmbH | How to run Flutter on an Embedded Device https://github.com/sony/flutter-embedded-linux/wiki/Building-Flutter-Engine-from-source flutter源码下载(最新)-CSDN博客 flutter_engine 交叉编译【自定义编译器(最新)】_flutter。engine 修改-CSDN博客 …...

airflow docker 安装

mkdir -p /root/airflow cd /root/airflow && mkdir -p ./dags ./logs ./plugins ./configcd /root/airflow/ wget https://airflow.apache.org/docs/apache-airflow/2.10.4/docker-compose.yaml nano docker-compose.yamlAIRFLOW__CORE__LOAD_EXAMPLES: false #初始化…...

浅析InnoDB引擎架构(已完结)

大家好&#xff0c;我是此林。 今天来介绍下InnoDB底层架构。 1. 磁盘架构 我们所有的数据库文件都保存在 /var/lib/mysql目录下。 由于我这边是docker部署的mysql&#xff0c;用如下命令查看mysql数据挂载。 docker inspect mysql-master 如下图&#xff0c;目前只有一个数…...

华为云计算HCIE笔记02

第二章&#xff1a;华为云Stack规划设计 交付总流程 准备工作&#xff1a;了解客户的基本现场&#xff0c;并且对客户的需求有基本的认知。 HLD方案BOQ报价设备采购和设备上架 2.安装部署流程 硬件架构设计 硬件设备选配 设备上架与初始化配置 准备相关资料&#xff08;自动下载…...

鸿蒙项目云捐助第十讲鸿蒙App应用分类页面二级联动功能实现

鸿蒙项目云捐助第十讲鸿蒙App应用分类页面二级联动功能实现 在之前的教程中完成了分类页面的左右两侧的列表结构&#xff0c;如下图所示。 接下来需要实现左侧分类导航项的点击操作&#xff0c;可以友好的提示用户选择了哪一个文字分类导航项。 一、左侧文字分类导航的处理 …...

STM32低功耗模式结合看门狗

STM32低功耗模式结合看门狗 前言 最近做到一个需求要使用STM32的低功耗模式进行长时间待机应用&#xff0c;每隔十分钟发送一次数据到服务器上&#xff0c;当不发送的时候就处于低功耗模式。在经过一段时间的测试以后发现板子过三四天左右就没有数据上传服务器了&#xff0c;…...

数据迁移工具,用这8种!

前言 最近有些小伙伴问我&#xff0c;ETL数据迁移工具该用哪些。 ETL(是Extract-Transform-Load的缩写&#xff0c;即数据抽取、转换、装载的过程)&#xff0c;对于企业应用来说&#xff0c;我们经常会遇到各种数据的处理、转换、迁移的场景。 今天特地给大家汇总了一些目前…...

Sapro编程软件

Sapro软件是由西门子建筑科技公司开发的一款编程软件&#xff0c;主要用于Climatix控制器的编程、调试及相关功能实现.以下是其具体介绍&#xff1a; • 功能强大&#xff1a;可进行HVAC控制编程&#xff0c;实现设备控制、HMI用户访问和设备集成等功能&#xff0c;满足复杂的…...

Python图注意力神经网络GAT与蛋白质相互作用数据模型构建、可视化及熵直方图分析...

全文链接&#xff1a;https://tecdat.cn/?p38617 本文聚焦于图注意力网络GAT在蛋白质 - 蛋白质相互作用数据集中的应用。首先介绍了研究背景与目的&#xff0c;阐述了相关概念如归纳设置与转导设置的差异。接着详细描述了数据加载与可视化的过程&#xff0c;包括代码实现与分析…...

2024年图像处理、多媒体技术与机器学习

重要信息 官网&#xff1a;www.ipmml.org 时间&#xff1a;2024年12月27-29日 地点&#xff1a;中国-大理 简介 2024年图像处理、多媒体技术与机器学习&#xff08;CIPMT 2024&#xff09;将于2024年12月27-29日于中国大理召开。将围绕图像处理与多媒体技术、机器学习等在…...

java 1.8+springboot文件上传+vue3+ts+antdv

1.参考 使用SpringBoot优雅的实现文件上传_51CTO博客_springboot 上传文件 2.postman测试 报错 &#xff1a;postman调用时body参数中没有file单词 Resolved [org.springframework.web.multipart.support.MissingServletRequestPartException: Required request part file is…...

【机器人】机械臂轨迹和转矩控制对比

动力学控制和轨迹跟踪控制是机器人控制中的两个概念&#xff0c;它们在目标、方法和应用上有所不同&#xff0c;但也有一定关联。以下是它们的区别和联系&#xff1a; 1. 动力学控制 动力学控制是基于机器人动力学模型的控制方法&#xff0c;目标是控制机器人关节力矩或力&…...

如何利用矩阵化简平面上的二次型曲线

二次型曲线的定义 在二维欧式平面上&#xff0c;一个二次型曲线都可以写成一个关于 x , y x,y x,y的二元二次多项式&#xff1a; F ( x , y ) a 11 x 2 2 a 12 x y a 22 y 2 2 a 1 x 2 a 2 y a 0 0 \begin{equation} F(x,y)a_{11}x^22a_{12}xya_{22}y^22a_1x2a_2ya_00…...

【系统移植】制作SD卡启动——将uboot烧写到SD卡

在开发板上启动Linux内核&#xff0c;一般有两种方法&#xff0c;一种是从EMMC启动&#xff0c;还有一种就是从SD卡启动&#xff0c;不断哪种启动方法&#xff0c;当开发板上电之后&#xff0c;首先运行的是uboot。 制作SD卡启动&#xff0c;首先要将uboot烧写到SD卡&#xff…...

sql server 数据库还原,和数据检查

右键数据库选择还原&#xff0c; 还原的备份文件必须选择在本地的文件&#xff08;远程文件没有试过&#xff09;还原数据库名字可以修改&#xff0c;然后file选择中有个2个目录data file 的目录 &#xff0c;和log data 的目录都可以重新选择还原到的新的目录&#xff0c;不要…...

工业大数据分析算法实战-day12

文章目录 day12时序分解STL&#xff08;季节性趋势分解法&#xff09;奇异谱分析&#xff08;SSA&#xff09;经验模态分解&#xff08;EMD&#xff09; 时序分割ChangpointTreeSplitAutoplait有价值的辅助 时序再表征 day12 今天是第12天&#xff0c;昨天主要是针对信号处理算…...

Hive其一,简介、体系结构和内嵌模式、本地模式的安装

目录 一、Hive简介 二、体系结构 三、安装 1、内嵌模式 2、测试内嵌模式 3、本地模式--最常使用的模式 一、Hive简介 Hive 是一个框架&#xff0c;可以通过编写sql的方式&#xff0c;自动的编译为MR任务的一个工具。 在这个世界上&#xff0c;会写SQL的人远远大于会写ja…...

LSTM-SVM时序预测 | Matlab基于LSTM-SVM基于长短期记忆神经网络-支持向量机时间序列预测

LSTM-SVM时序预测 | Matlab基于LSTM-SVM基于长短期记忆神经网络-支持向量机时间序列预测 目录 LSTM-SVM时序预测 | Matlab基于LSTM-SVM基于长短期记忆神经网络-支持向量机时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.LSTM-SVM时序预测 | Matlab基于LSTM…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...