后端开发刷题 | 合并两个排序的链表
描述
输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围: 0≤n≤1000,−1000≤节点值≤1000
如输入{1,3,5},{2,4,6}时,合并后的链表为{1,2,3,4,5,6},所以对应的输出为{1,2,3,4,5,6},转换过程如下图所示:

或输入{-1,2,4},{1,3,4}时,合并后的链表为{-1,1,2,3,4,4},所以对应的输出为{-1,1,2,3,4,4},转换过程如下图所示:

示例1
输入:
{1,3,5},{2,4,6}
返回值:
{1,2,3,4,5,6}
示例2
输入:
{},{}
返回值:
{}
示例3
输入:
{-1,2,4},{1,3,4}
返回值:
{-1,1,2,3,4,4}
思路分析:
方法一:
使用递归来进行求解
- 终止条件:两链表其中一个为空时,返回另一个链表;
- 当前递归内容:若pHead1
.val <=pHead2.val将较小的pHead1.next与merge后的表头连接,即pHead1.next = Merge(pHead1.next,pHead2);pHead2.val较大时同理; - 每次的返回值:排序好的链表头;
复杂度:O(m+n) O(m+n)
代码:
import java.util.*;public class Solution {/*** * @param pHead1 ListNode类 * @param pHead2 ListNode类 * @return ListNode类*/public ListNode Merge (ListNode pHead1, ListNode pHead2) {if(pHead1==null){return pHead2;}if(pHead2==null){return pHead1;}if(pHead1.val>pHead2.val){pHead2.next=Merge(pHead1,pHead2.next);return pHead2;}else{pHead1.next=Merge(pHead1.next,pHead2);return pHead1;}}
}
方法二:
空间O(1)的思路:
-
创建一个虚拟结点和一个哨兵结点
-
当pHead1与pHead
2都不为null时循环 -
哪个的
val小哪个赋给虚拟结点的next,虚拟结点后移。 -
退出循环后,哪个pHead不为空,哪个结点(包括剩下的)给虚拟结点的
next -
最后返回哨兵结点的
next
代码:
import java.util.*;public class Solution {/*** * @param pHead1 ListNode类 * @param pHead2 ListNode类 * @return ListNode类*/public ListNode Merge (ListNode pHead1, ListNode pHead2) {ListNode dummy=new ListNode(-1);ListNode res=dummy;while(pHead1!=null&&pHead2!=null){if(pHead1.val>pHead2.val){dummy.next=pHead2;pHead2=pHead2.next;dummy=dummy.next;}else if(pHead1.val<=pHead2.val){dummy.next=pHead1;pHead1=pHead1.next;dummy=dummy.next;}}if(pHead1!=null){dummy.next=pHead1;}if(pHead2!=null){dummy.next=pHead2;}return res.next;}
}
相关文章:
后端开发刷题 | 合并两个排序的链表
描述 输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的。 数据范围: 0≤n≤1000,−1000≤节点值≤1000 如输入{1,3,5},{2,4,6}时,合并后的链表为{1,2,3,4,5,6},…...
JAVA_7
JAVA_7 JAVA面向对象编程1. 抽象方法和抽象类 JAVA面向对象编程 1. 抽象方法和抽象类 使用abstract修饰的方法,没有方法体,只有声明。定义的是一种“规范”,就是告诉子类必须要给抽象方法提供具体的实现。包含抽象方法的类就是抽象类。通过…...
最大连续1的个数 III(LeetCode)
题目 给定一个二进制数组 nums 和一个整数 k,如果可以翻转最多 k 个 0 ,则返回 数组中连续 1 的最大个数 。 解题 def longestOnes(nums, k):left 0max_len 0zero_count 0for right in range(len(nums)):# 如果遇到0,统计当前窗口内0的个…...
Vue之前端批量下载文件并以压缩包形式存储
后端返回一个文件链接的数组,前端处理下载逻辑,并且将这些文件存储在压缩包内部,这用的jszip 和 file-saver 这两个库。 步骤说明 1.使用 npm 或 yarn 安装 jszip 和 file-saver。 npm install jszip file-saver 2.获取文件内容:…...
【AI学习】LLaMA模型的微调成本有几何?
在前面文章《LLaMA 系列模型的进化(二)》中提到了Stanford Alpaca模型。 Stanford Alpaca 基于LLaMA (7B) 进行微调,通过使用 Self-Instruct 方法借助大语言模型进行自动化的指令生成,Stanford Alpaca 生成了 52K 条指令遵循样例数…...
【专题】2024全数驱动 致胜未来-数字化敏捷银行白皮书报告合集PDF分享(附原数据表)
原文链接: https://tecdat.cn/?p37404 政策明确发展使命,新时代商业银行应坚持党建引领,秉持高质量发展理念。数字经济已成大势,商业银行需构建数字基础设施能力,强化顶层战略规划。当前商业银行数字化发展面临诸多挑…...
280Hz显示器哪家强
280Hz显示器哪家强?今天就给大家带来6大品牌和型号的280Hz显示器一起对比对比! 1.280Hz显示器 - HKC G27H3显示器 HKC G27H3是一款高性价比的电竞显示器,以下是它的一些特点: - **高刷新率与快速响应**: - 拥有280H…...
ROUTE_STATUS
ROUTE_STATUS是一个只读属性,由Vivado路由器分配给网络 反映网络上路由的当前状态。 该属性可以由单个网络或一组网络使用 get_property或report_property命令。该物业由 report_route_status命令返回整个设计的route_status。 架构支持 所有架构。 适用对象 •网络…...
v4l2(video4linux2) yuyv(yuv422)、MJPEG、H.264
V4L2(Video4Linux2)是Linux内核中的视频设备接口框架,专门用于捕获和输出视频数据。V4L2广泛应用于各种视频设备的驱动程序开发,如网络摄像头、电视调谐器、视频采集卡、以及其他视频输入/输出设备。 ### V4L2的主要功能 1. **视…...
.Net插件开发开源框架
在.NET开发中,有许多开源框架可以用于插件开发,以下是一些最常见的框架: MEF(Managed Extensibility Framework) MEF是一个用于创建可插拔软件应用程序的库,它可以在不修改原始应用程序的情况下扩展应用程…...
基于Spark实现大数据量的Node2Vec
基于Spark实现大数据量的Node2Vec Node2Vec 是一种基于图的学习算法,用于生成图中节点的低维度、高质量的向量表示。这种算法基于 word2vec 模型,将自然语言处理中的词嵌入技术应用于图结构的节点,以捕捉节点之间的复杂关系。Node2Vec 特别强…...
[VMware]VMware-Esxi 6.7 厚置备转为精简置备
背景:创建了一个win10 60G的厚置备磁盘,现在想改为精简置备。 先关闭win10系统,并删除快照 1、开启shell 2、登录到虚拟存放的目录 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 [rootxxx:~] cd /vmfs/volumes/5fea055e-458157d3-c8f8-8cec4ba51c4…...
vue面试题十八
一、Vue 3中的样式绑定有哪些新特性? Vue 3中的样式绑定保持了与Vue 2相似的灵活性和强大功能,同时引入了一些新的特性和改进,主要集中在响应式系统和Composition API上。以下是Vue 3中样式绑定的主要新特性及其说明: 1. 响应式…...
windows C++-windows C++/CX简介(三)
^类型 (^) 是 C/CX 最突出的功能之一——当人们第一次看到 C/CX 代码时,很难不注意到它。那么,^ 类型到底是什么?这是类型是一种智能指针类型,它自动管理 Windows 运行时对象的生命周期,也 提供自动类型转换功能以简化…...
《黑神话.悟空》:一场跨越神话与现实的深度探索
《黑神话.悟空》:一场跨越神话与现实的深度探索 在国产游戏日益崛起的今天,《黑神话.悟空》以其独特的剧情、丰富的人物设定和深刻的主题,成为了无数玩家翘首以盼的国产3A大作。这款游戏不仅是一次对传统故事的创新演绎,更是一场对…...
【Kotlin设计模式】建造者模式在Android中的应用
前言 建造者模式(Builder Pattern)是一种创建型设计模式,一步一步地构建一个复杂对象的不同部分,而不是直接创建该对象的实例。建造者模式的核心思想是将对象的构建过程与其表示分离,使得同样的构建过程可以创建不同的…...
Kafka 性能为什么比 RocketMQ 好
Kafka 性能更好的原因 因为 kafka 零拷贝技术跟 RocketMQ 的不一样。 kafka 零拷贝技术使用的是 sendfileDMA scatter/gather 。只需要经过 2 次拷贝,2 次上下文切换RocketMQ 零拷贝使用的 mmap 内存映射,需要经过 3 次拷贝,4 次上下文切换…...
el-image的配套使用(表格,表单)
1. 配合table在一起使用,支持预览 此处使用场景是表格中只显示一张图片 preview-src-list只支持数组,故需要将单个字符串转换为转换为字符串数组 <el-table-column align"center" label"二维码"><template slot-scope&q…...
MKS MWH-5匹配器Automatc matching impedance Network手侧
MKS MWH-5匹配器Automatc matching impedance Network手侧...
打卡50天------图论
正式开启图论了,作为一个前端工程师,这个代码随想录真的刷新了我对于算法的认知,每天都在学习新东西。 别着急、放轻松、慢慢来。 一、图论理论基础 二、深搜理论基础 了解一下深搜的原理和过程,其实对于深搜和广搜我自己也写过…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
