当前位置: 首页 > 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…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

掌握 HTTP 请求:理解 cURL GET 语法

cURL 是一个强大的命令行工具&#xff0c;用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中&#xff0c;cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...