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

LeetCode23.合并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

思路

要将多个已按升序排列的链表合并成一个升序链表,可以使用分治法的思想。我们利用分治法的思想,递归地将链表数组拆分成两部分,然后合并这些部分,最终得到一个合并后的升序链表。

  • 定义一个辅助函数mergeTwoLists(ListNode* list1, ListNode* list2),用于合并两个链表的方法,这是我们之前讨论过的合并两个升序链表的方法。

  • 在mergeKLists函数中,首先判断输入的链表数组是否为空,如果为空则返回nullptr。

  • 利用分治法的思想,将链表数组不断地拆分成两部分,然后递归地合并这些部分,直到只剩下一个链表为止。具体步骤如下:

    • 计算链表数组的中间位置mid,将链表数组拆分成两部分:左半部分为[0, mid-1],右半部分为[mid, size-1]。
    • 递归调用mergeKLists函数,分别对左右两部分进行合并,得到leftList和rightList。
    • 最终,再调用mergeTwoLists方法将leftList和rightList合并为一个新的升序链表,并返回合并后的结果。
  • 最终返回合并后的链表即可。

Code:

class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {if (lists.empty()) {return nullptr;}return merge(lists, 0, lists.size() - 1);}private:ListNode* merge(vector<ListNode*>& lists, int left, int right) {if (left == right) {return lists[left];}if (left < right) {int mid = left + (right - left) / 2;ListNode* leftList = merge(lists, left, mid);ListNode* rightList = merge(lists, mid + 1, right);return mergeTwoLists(leftList, rightList);}return nullptr;}ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (!list1) {return list2;}if (!list2) {return list1;}if (list1->val < list2->val) {list1->next = mergeTwoLists(list1->next, list2);return list1;} else {list2->next = mergeTwoLists(list1, list2->next);return list2;}}
};

相关文章:

LeetCode23.合并K个升序链表

题目 给你一个链表数组&#xff0c;每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中&#xff0c;返回合并后的链表。 示例 &#xff1a; 输入&#xff1a;lists [[1,4,5],[1,3,4],[2,6]] 输出&#xff1a;[1,1,2,3,4,4,5,6] 解释&#xff1a;链表数组如下&…...

(01)Hive的相关概念——架构、数据存储、读写文件机制

目录 一、架构及组件介绍 1.1 Hive整体架构 1.2 Hive组件 1.3 Hive数据模型&#xff08;Data Model&#xff09; 1.3.1 Databases 1.3.2 Tables 1.3.3 Partitions 1.3.4 Buckets 二、Hive读写文件机制 2.1 SerDe 作用 2.2 Hive读写文件流程 2.2.1 读取文件的过程 …...

二维码扫码登录原理,其实比你想的要简单的多

二维码&#xff0c;大家再熟悉不过了 购物扫个码&#xff0c;吃饭扫个码&#xff0c;坐公交也扫个码 在扫码的过程中&#xff0c;大家可能会有疑问&#xff1a;这二维码安全吗&#xff1f; 会不会泄漏我的个人信息&#xff1f; 更深度的用户还会考虑&#xff1a;我的系统是不…...

Java 实现 Awaitable(多线程并行等待,类似 AutoEventReset 的作用)

AutoEventReset、ManualEventReset&#xff0c;是我们在多线程并行编程之中常常需要涉及的&#xff0c;但是 ManualEventReset 可能用的并没有那么多&#xff0c;这个多用于实现读写锁的&#xff0c;当然 Java 自己库提供了官方实现&#xff0c;就没必要自己去整了。 C/C 里面…...

AI之Sora:Sora(文本指令生成视频的里程碑模型)的简介(能力/安全性/技术细节)、使用方法、案例应用之详细攻略

AI之Sora&#xff1a;Sora(文本指令生成视频的里程碑模型)的简介(能力/安全性/技术细节)、使用方法、案例应用之详细攻略 导读&#xff1a;Sora 是OpenAI研发的一个可以根据文字描述生成视频的AI模型。它的主要特性、功能以及OpenAI在安全和应用方面的策略的核心要点如下所示&a…...

IListManger feeds流

目的:将feeds的分页加载和下拉刷新,与网络请求关联起来 ListLibRecyclerViewProxy 在this.getRecyclerView().addOnScrollListener中记录事件 recyclerView.computeVerticalScrollOffset() // 已经向下滚动的距离,为0时表示已处于顶部。 recyclerView.computeVerticalScro…...

视频推拉流EasyDSS视频直播点播平台授权出现激活码无效并报错400是什么原因?

视频推拉流EasyDSS视频直播点播平台集视频直播、点播、转码、管理、录像、检索、时移回看等功能于一体&#xff0c;可提供音视频采集、视频推拉流、播放H.265编码视频、存储、分发等视频能力服务&#xff0c;在应用场景上&#xff0c;平台可以运用在互联网教育、在线课堂、游戏…...

设计模式三:工厂模式

工厂模式包括简单工厂模式、工厂方法模式和抽象工厂模式&#xff0c;其中后两者属于23中设计模式 各种模式中共同用到的实体对象类&#xff1a; //汽车类&#xff1a;宝马X3/X5/X7&#xff1b;发动机类&#xff1a;B48TU、B48//宝马汽车接口 public interface BMWCar {void s…...

2024.2.15 模拟实现 RabbitMQ —— 消息持久化

目录 引言 约定存储方式 消息序列化 重点理解 针对 MessageFileManager 单元测试 小结 统一硬盘操作​​​​​​​ 引言 问题&#xff1a; 关于 Message&#xff08;消息&#xff09;为啥在硬盘上存储&#xff1f; 回答&#xff1a; 消息操作并不涉及到复杂的增删查改消…...

【技巧】金融企业在搭建服务器时,选择私有云方案还是全栈专属云?

金融企业在搭建服务器时&#xff0c;选择私有云方案还是全栈专属云&#xff0c;需要根据企业的具体需求和情况进行综合考虑。Cloud Ace云一作为谷歌云全球战略合作伙伴&#xff0c;专注于企业级出海云服务 &#xff0c;为大家带来两种方案的优劣势比较&#xff1a; 私有云 优势…...

【大厂AI课学习笔记】【2.2机器学习开发任务实例】(10)模型评测

目录 一、模型评测的定义 二、模型评测的方法 三、模型评测的原理 四、涉及的关键技术 五、实例阐述 今天是2.2机器学习开发任务实例的最后一个部分——模型评测。 不同的模型计算出的MSE值会有差异&#xff0c;通过模型的选择&#xff0c;参数的变换&#xff0c;可以比较…...

【C++游戏开发-03】贪吃蛇

文章目录 前言一、工具准备1.1游戏开发框架1.2visual studio2022下载1.3easyX下载1.4图片素材 二、逻辑分析2.1数据结构2.2蛇的移动2.3吃食物2.4游戏失败 三、DEMO代码实现四、完整源代码总结 &#x1f431;‍&#x1f680;个人博客https://blog.csdn.net/qq_51000584?typeblo…...

如何理解CSS的边框宽度?

CSS 边框宽度学习手记 CSS 边框宽度小概念 在CSS的世界里&#xff0c;border-width这个属性真的很实用&#xff0c;它能帮我指定HTML元素四周边框的宽度。这个宽度嘛&#xff0c;可以用像素px、点pt、厘米cm、相对单位em这些来表示&#xff0c;很方便吧&#xff01;还有呢&am…...

java 写入写出 zip

package com.su.test.aaaTest.ioTest; import java.io.File; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IOException; import java.util.zip.ZipEntry; import java.util.zip.ZipOutputStream; /** 将文件压缩到 zip 中 */ public c…...

问题解决:‘telnet‘ 不是内部或外部命令,也不是可运行的程序 或批处理文件

当在windows终端中运行telnet指令的时候&#xff0c;发现指令不可用&#xff0c;原因在于系统没安装telnet功能。 解决方法&#xff1a; 打开控制面板–》程序–》启用或关闭windows功能–》勾选Telnet客户端&#xff0c;点击确定即可。...

从基础到高级:Linux用户与用户组权限设置详解

目录 博客前言&#xff1a; 一.简介 1.用户的定义 用户账户分类 2.用户组的定义 二.用户的相关linux语法 1.创建用户&#xff08;useradd&#xff09; 2.删除用户&#xff08;userdel&#xff09; 3.修改用户&#xff08;usermod&#xff09; 4.修改用户密码 5.su切…...

【感知机】感知机(perceptron)学习算法知识点汇总

机器学习——感知机 感知机(perceptron)是一种二分类的线性模型&#xff0c;属于判别模型&#xff0c;也称为线性二分类器。输入为实例的特征向量&#xff0c;输出为实例的类别(取1和-1)。可以视为一种使用阶梯函数激活的人工神经元,例如通过梅尔频率倒谱系数&#xff08;MFCC…...

蓝桥杯:C++二分算法

在基本算法中&#xff0c;二分法的应用非常广泛&#xff0c;它是一种思路简单、编程容易、效率极高的算法。蓝桥杯软件类大赛中需要应用二分法的题目很常见。 二分法有整数二分和实数二分两种应用场景 二分法的概念 二分法的概念很简单&#xff0c;每次把搜索范围缩小为上一…...

Leetcode刷题笔记题解(C++):83. 删除排序链表中的重复元素

思路&#xff1a;链表相关的问题建议就是画图去解决&#xff0c;虽然理解起来很容易&#xff0c;但就是写代码写不出来有时候&#xff0c;依次去遍历第二节点如果与前一个节点相等则跳过&#xff0c;不相等则遍历第三个节点 /*** Definition for singly-linked list.* struct …...

@ 代码随想录算法训练营第8周(C语言)|Day56(动态规划)

代码随想录算法训练营第8周&#xff08;C语言&#xff09;|Day56&#xff08;动态规划&#xff09; Day56、动态规划&#xff08;包含题目 ● 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组 &#xff09; 300.最长递增子序列 题目描述 给你一个整数…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

MVC 数据库

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

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...