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

后端开发刷题 | 合并两个排序的链表

描述

输入两个递增的链表,单个链表的长度为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与pHead2都不为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;}
}

相关文章:

后端开发刷题 | 合并两个排序的链表

描述 输入两个递增的链表&#xff0c;单个链表的长度为n&#xff0c;合并这两个链表并使新链表中的节点仍然是递增排序的。 数据范围&#xff1a; 0≤n≤1000&#xff0c;−1000≤节点值≤1000 如输入{1,3,5},{2,4,6}时&#xff0c;合并后的链表为{1,2,3,4,5,6}&#xff0c;…...

JAVA_7

JAVA_7 JAVA面向对象编程1. 抽象方法和抽象类 JAVA面向对象编程 1. 抽象方法和抽象类 使用abstract修饰的方法&#xff0c;没有方法体&#xff0c;只有声明。定义的是一种“规范”&#xff0c;就是告诉子类必须要给抽象方法提供具体的实现。包含抽象方法的类就是抽象类。通过…...

最大连续1的个数 III(LeetCode)

题目 给定一个二进制数组 nums 和一个整数 k&#xff0c;如果可以翻转最多 k 个 0 &#xff0c;则返回 数组中连续 1 的最大个数 。 解题 def longestOnes(nums, k):left 0max_len 0zero_count 0for right in range(len(nums)):# 如果遇到0&#xff0c;统计当前窗口内0的个…...

Vue之前端批量下载文件并以压缩包形式存储

后端返回一个文件链接的数组&#xff0c;前端处理下载逻辑&#xff0c;并且将这些文件存储在压缩包内部&#xff0c;这用的jszip 和 file-saver 这两个库。 步骤说明 1.使用 npm 或 yarn 安装 jszip 和 file-saver。 npm install jszip file-saver 2.获取文件内容&#xff1a…...

【AI学习】LLaMA模型的微调成本有几何?

在前面文章《LLaMA 系列模型的进化&#xff08;二&#xff09;》中提到了Stanford Alpaca模型。 Stanford Alpaca 基于LLaMA (7B) 进行微调&#xff0c;通过使用 Self-Instruct 方法借助大语言模型进行自动化的指令生成&#xff0c;Stanford Alpaca 生成了 52K 条指令遵循样例数…...

【专题】2024全数驱动 致胜未来-数字化敏捷银行白皮书报告合集PDF分享(附原数据表)

原文链接&#xff1a; https://tecdat.cn/?p37404 政策明确发展使命&#xff0c;新时代商业银行应坚持党建引领&#xff0c;秉持高质量发展理念。数字经济已成大势&#xff0c;商业银行需构建数字基础设施能力&#xff0c;强化顶层战略规划。当前商业银行数字化发展面临诸多挑…...

280Hz显示器哪家强

280Hz显示器哪家强&#xff1f;今天就给大家带来6大品牌和型号的280Hz显示器一起对比对比&#xff01; 1.280Hz显示器 - HKC G27H3显示器 HKC G27H3是一款高性价比的电竞显示器&#xff0c;以下是它的一些特点&#xff1a; - **高刷新率与快速响应**&#xff1a; - 拥有280H…...

ROUTE_STATUS

ROUTE_STATUS是一个只读属性&#xff0c;由Vivado路由器分配给网络 反映网络上路由的当前状态。 该属性可以由单个网络或一组网络使用 get_property或report_property命令。该物业由 report_route_status命令返回整个设计的route_status。 架构支持 所有架构。 适用对象 •网络…...

v4l2(video4linux2) yuyv(yuv422)、MJPEG、H.264

V4L2&#xff08;Video4Linux2&#xff09;是Linux内核中的视频设备接口框架&#xff0c;专门用于捕获和输出视频数据。V4L2广泛应用于各种视频设备的驱动程序开发&#xff0c;如网络摄像头、电视调谐器、视频采集卡、以及其他视频输入/输出设备。 ### V4L2的主要功能 1. **视…...

.Net插件开发开源框架

在.NET开发中&#xff0c;有许多开源框架可以用于插件开发&#xff0c;以下是一些最常见的框架&#xff1a; MEF&#xff08;Managed Extensibility Framework&#xff09; MEF是一个用于创建可插拔软件应用程序的库&#xff0c;它可以在不修改原始应用程序的情况下扩展应用程…...

基于Spark实现大数据量的Node2Vec

基于Spark实现大数据量的Node2Vec Node2Vec 是一种基于图的学习算法&#xff0c;用于生成图中节点的低维度、高质量的向量表示。这种算法基于 word2vec 模型&#xff0c;将自然语言处理中的词嵌入技术应用于图结构的节点&#xff0c;以捕捉节点之间的复杂关系。Node2Vec 特别强…...

[VMware]VMware-Esxi 6.7 厚置备转为精简置备

背景&#xff1a;创建了一个win10 60G的厚置备磁盘&#xff0c;现在想改为精简置备。 先关闭win10系统&#xff0c;并删除快照 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中的样式绑定有哪些新特性&#xff1f; Vue 3中的样式绑定保持了与Vue 2相似的灵活性和强大功能&#xff0c;同时引入了一些新的特性和改进&#xff0c;主要集中在响应式系统和Composition API上。以下是Vue 3中样式绑定的主要新特性及其说明&#xff1a; 1. 响应式…...

windows C++-windows C++/CX简介(三)

^类型 (^) 是 C/CX 最突出的功能之一——当人们第一次看到 C/CX 代码时&#xff0c;很难不注意到它。那么&#xff0c;^ 类型到底是什么&#xff1f;这是类型是一种智能指针类型&#xff0c;它自动管理 Windows 运行时对象的生命周期&#xff0c;也 提供自动类型转换功能以简化…...

《黑神话.悟空》:一场跨越神话与现实的深度探索

《黑神话.悟空》&#xff1a;一场跨越神话与现实的深度探索 在国产游戏日益崛起的今天&#xff0c;《黑神话.悟空》以其独特的剧情、丰富的人物设定和深刻的主题&#xff0c;成为了无数玩家翘首以盼的国产3A大作。这款游戏不仅是一次对传统故事的创新演绎&#xff0c;更是一场对…...

【Kotlin设计模式】建造者模式在Android中的应用

前言 建造者模式&#xff08;Builder Pattern&#xff09;是一种创建型设计模式&#xff0c;一步一步地构建一个复杂对象的不同部分&#xff0c;而不是直接创建该对象的实例。建造者模式的核心思想是将对象的构建过程与其表示分离&#xff0c;使得同样的构建过程可以创建不同的…...

Kafka 性能为什么比 RocketMQ 好

Kafka 性能更好的原因 因为 kafka 零拷贝技术跟 RocketMQ 的不一样。 kafka 零拷贝技术使用的是 sendfileDMA scatter/gather 。只需要经过 2 次拷贝&#xff0c;2 次上下文切换RocketMQ 零拷贝使用的 mmap 内存映射&#xff0c;需要经过 3 次拷贝&#xff0c;4 次上下文切换…...

el-image的配套使用(表格,表单)

1. 配合table在一起使用&#xff0c;支持预览 此处使用场景是表格中只显示一张图片 preview-src-list只支持数组&#xff0c;故需要将单个字符串转换为转换为字符串数组 <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天------图论

正式开启图论了&#xff0c;作为一个前端工程师&#xff0c;这个代码随想录真的刷新了我对于算法的认知&#xff0c;每天都在学习新东西。 别着急、放轻松、慢慢来。 一、图论理论基础 二、深搜理论基础 了解一下深搜的原理和过程&#xff0c;其实对于深搜和广搜我自己也写过…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...