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

23. 合并 K 个升序链表

题目描述

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

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

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

解答

/*** 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:// 分治合并的方法// 若有k个链表,第一轮两两合并,得到 k/2 个链表 // 第二轮再两两合并,得 k / 4个链表,依此类推,剩余一个链表然后再自底向上合并ListNode* mergeKLists(vector<ListNode*>& lists) {return merge(lists, 0, lists.size() - 1);}ListNode* mergeKLists1(vector<ListNode*>& lists) {// 顺序合并ListNode *ans = nullptr; // 初始和一个空链表合并,便于操作for(size_t i = 0; i < lists.size(); ++i){ans = mergeTwoLists(ans, lists[i]);}return ans;}private:// 将 lists中下标从[l, r]的链表进行合并ListNode *merge(vector<ListNode*>& lists, int l, int r){if(l == r) return lists[l];if(l > r) return nullptr;int mid = (l + r) >> 1; // 拆分成两部分进行合并return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));}// 两个链表进行归并排序ListNode* mergeTwoLists(ListNode *a, ListNode *b){if((!a) || (!b)) return a ? a : b;ListNode head, *tail = &head, *aptr = a, *bptr = b;// 归并,尾插入列表while(aptr && bptr){if(aptr->val < bptr->val){tail->next = aptr;aptr = aptr->next;}else {tail->next = bptr;bptr = bptr->next;}tail = tail->next;}// 处理还有节点的链表,添加到结尾tail->next = aptr ? aptr : bptr;return head.next;}};

相关文章:

23. 合并 K 个升序链表

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

Nexus3部署、配置+SpringBoot项目Demo

Docker部署Nexus 搜索Nexus3镜像&#xff1a;[rootlocalhost ~]# docker search nexus 拉取Nexus3镜像&#xff1a;[rootlocalhost ~]# docker pull sonatype/nexus3 启动Nexus3前查看虚拟机端口是否被占用&#xff1a;[rootlocalhost ~]# netstat -nultp 通过Docker Hub查看安…...

linux下用docker安装mysql

1.mysql Docker镜像 docker pull mysql:[版本号 或 latest]例&#xff1a;docker pull mysql:5.7 2.查看拉取的docker镜像 docker images3.设置 Docker 卷 docker volume create mysql-data列出 Docker 已知的所有卷 docker volume ls4.运行一个 MySQL Docker 容器 docke…...

Vue - 可视化用户角色、菜单权限、按钮权限配置(动态获取菜单路由)

GitHub Demo 地址 在线预览 前言 关于动态获取路由已在这里给出方案 Vue - vue-admin-template模板项目改造&#xff1a;动态获取菜单路由 这里是在此基础上添加了系统管理模块&#xff0c;包含用户管理&#xff0c;角色管理&#xff0c;菜单管理&#xff0c;字典管理&#xf…...

hive库操作示例

hive库操作示例 1、常规表 创建数据库 CREATE DATABASE mydatabase;使用数据库 USE mydatabase;创建表 CREATE TABLE mytable (id INT,name STRING,age INT ) ROW FORMAT DELIMITED FIELDS TERMINATED BY , STORED AS TEXTFILE;插入数据 INSERT INTO TABLE mytable VALUE…...

LeetCode第 N 个泰波那契数 (认识动态规划)

认识动态规划 编写代码代码空间优化 链接: 第 N 个泰波那契数 编写代码 class Solution { public:int tribonacci(int n) {if(n 0){return 0;}else{if(n 1 || n 2)return 1;}vector<int> dp(n 1);dp[0] 0;dp[1] 1;dp[2] 1;for(int i 3;i < n;i){dp[i] dp[i-3]…...

线程安全问题(内存可见性)

导致的原因 内存可见性问题的出现主要是因为编译器优化多线程导致的 示例代码 package 线程安全问题;import java.util.Scanner;/*** Created with IntelliJ IDEA.* Description:* User: wuyulin* Date: 2023-07-26* Time: 13:49*/ public class Demo2 {private volatile sta…...

STM32MX配置EEPROM(AT24C02)------保姆级教程

———————————————————————————————————— ⏩ 大家好哇&#xff01;我是小光&#xff0c;嵌入式爱好者&#xff0c;一个想要成为系统架构师的大三学生。 ⏩最近在开发一个STM32H723ZGT6的板子&#xff0c;使用STM32CUBEMX做了很多驱动&#x…...

微信小程序 样式和全局配置

WXSS wxss 把屏幕分为750个物理像素&#xff0c;大屏大&#xff0c;小屏小&#xff0c;随着设备不一致自动适配 推荐使用iPhone6作为标准&#xff0c;1个rpx 0.5个px&#xff0c;把px乘以2就是rpx的参数 import 导入外部样式表 import /common/common.wxss 样式 权重一…...

一.初识C语言

一.初识C语言 C语言标准规定&#xff1a; sizeof(long)>sizeof(int)就可以了变量要定义在当前代码块的最前面 #defin _CRT_SECURE_NO_WARNINGS 1#include <stdio.h> //包含一个stdio.h的文件 std-标准standard input outputint main() //主函数-程序的入口-main函数…...

filebeat到kafka示例

docker run -d \ --namefilebeat_7.14_0 \ #filebeat名称 --userroot \ --volume"/data/filebeat/filebeat.yml:/usr/share/filebeat/filebeat.yml" \ #映射filebeat.yml配置 --volume"/data/filebeat/log:/usr/share/filebeat/log" \…...

AlmaLinux系统下的Zabbix汉化

我安装的是zabbix下的虚拟机&#xff0c;安装完成后&#xff0c;直接可以打开网站了&#xff0c;但是界面是英文&#xff0c;看了设置&#xff0c;没有中文选项&#xff0c;就需要在系统中安装中文字符集了。 # locale -a #查看里面没有zh_CN之类的项 # dnf install -…...

【网络编程】(TCP流套接字编程 ServerSocket API Socket API 手写TCP版本的回显服务器 TCP中的长短连接)

文章目录 网络编程TCP流套接字编程ServerSocket APISocket APITCP中的长短连接手写TCP版本的回显服务器 网络编程 TCP流套接字编程 TCP提供的API主要是两个类:ServerSocket 和 Socket . TCP不需要一个类来表示"TCP数据报"因为TCP不是以数据报为单位进行传输的.是以…...

企业级PaaS低代码快开平台源码,基于 Salesforce Platform 的开源替代方案

PaaS低代码快开平台是一种快速开发应用系统的工具&#xff0c;用户通过少量代码甚至不写代码就可以快速构建出各种应用系统。 随着信息化技术的发展&#xff0c;企业对信息化开发的需求正在逐渐改变&#xff0c;传统的定制开发已经无法满足企业需求。低代码开发平台&#xff0…...

【LeetCode】72.编辑距离

题目 给你两个单词 word1 和 word2&#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作&#xff1a; 插入一个字符删除一个字符替换一个字符 示例 1&#xff1a; 输入&#xff1a;word1 "horse", word2 "…...

大模型,开源干不掉闭源

开源大模型对闭源大模型的冲击&#xff0c;变得非常猛烈。 今年3月&#xff0c;Meta发布了Llama&#xff08;羊驼&#xff09;&#xff0c;很快成为AI社区内最强大的开源大模型&#xff0c;也是许多模型的基座模型。有人戏称&#xff0c;当前的大模型集群&#xff0c;就是一堆各…...

Redis 九种数据类型的基本操作

一、redis9种数据类型的基本操作 ①key操作 #查找所有的key 127.0.0.1:6379> keys * 1) "pop" 2) "mylist" 3) "lpl" 4) "myset" #设置key的过期时间 返回1表示执行成功&#xff0c;0表示失败&#xff0c;出现问题 127.0.0.1:6379…...

爬取微博热搜榜并进行数据分析

设计方案 爬虫爬取的内容 &#xff1a;爬取微博热搜榜数据。 网络爬虫设计方案概述 用requests库访问页面用get方法获取页面资源&#xff0c;登录页面对页面HTML进行分析&#xff0c;用beautifulsoup库获取并提取自己所需要的信息。再讲数据保存到CSV文件中&#xff0c;进行…...

基于深度神经网络的肺炎检测系统实现

一、说在前面 使用AI进行新冠肺炎图像诊断可以加快病例的诊断速度&#xff0c;提高诊断的准确性&#xff0c;并在大规模筛查中发挥重要作用&#xff0c;从而更好地控制和管理这一流行病。然而&#xff0c;需要强调的是&#xff0c;AI技术仅作为辅助手段&#xff0c;最终的诊断决…...

C# LINQ和Lambda表达式对照

C# LINQ和Lambda表达式对照 1. 基本查询语句 Linq语法&#xff1a; var datafrom a in db.Areas select a ; Lamda语法&#xff1a; var datadb.Areas; sql语法&#xff1a; SELECT * FROM Areas2. 简单的WHERE语句 Linq语法&#xff1a; var datafrom a in db.orderI…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

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

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