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

【链表OJ题(五)】合并两个有序链表

在这里插入图片描述

​📝个人主页:@Sherry的成长之路
🏠学习社区:Sherry的成长之路(个人社区)
📖专栏链接:数据结构
🎯长路漫漫浩浩,万事皆有期待

文章目录

  • 链表OJ题(五)
    • 1. 合并两个有序链表
      • 1.1 思路--带哨兵位的头结点
      • 1.2 思路--不强行加头结点
  • 2.总结:

上一篇链表OJ题链接:【链表OJ题(四)】反转链表

链表OJ题(五)

1. 合并两个有序链表

链接:21. 合并两个有序链表

描述:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
在这里插入图片描述

示例1:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例2:
输入:l1 = [], l2 = []
输出:[]
示例3:
输入:l1 = [], l2 = [0]
输出:[0]

提示:
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

1.1 思路–带哨兵位的头结点

之前做过一道题目,叫做合并两个有序数组。其中有一种方法是创建一个新数组,然后遍历两个数组,将两个数组的较小的元素放置到新数组中。一个数组遍历完,将没有放置的元素放置到新数组中,然后拷贝回原数组。

那么这道题能否借鉴它的思路?
合并两个有序链表,链表和数组不同,数组形式的一种方法需要我们创建一个新数组。但是对于链表而言我们可以通过指针改变链接关系,所以不需要创建新链表,只需要修改即可。
有序数组的做法是将较小元素逐个尾插到新数组中,那么我们也可以将较小元素尾插到链表中

那么链表为空如何处理?
这时就又要用到哨兵位(头结点)了,我们给一个哨兵位 head,它也不存储数据,那么不就可以了?但是注意有效数据从 head->next 开始。
在这里插入图片描述

但是尾插存在两个问题,当尾插的时候,我们需要找链表的尾,而且当链表为空时,需要特殊处理。为了避免每次找链表的尾,那么我们就给定一个 tail,这样只要将 tail 迭代就可以。
在这里插入图片描述

注意:哨兵位需要释放,否则会造成内存泄漏。
在这里插入图片描述

代码:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* head = NULL, *tail = NULL;if (list1 == NULL){return list2;} if (list2 == NULL){return list1;}// 哨兵位// 这里 tail 也需要动态开辟一下// 因为不在迭代时进行第一次插入的处理// tail 一开始为空指针,会报错head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));   while (list1 && list2){if (list1->val < list2->val){tail->next = list1; // 当前结点链表的尾链接到 list1tail = list1; // 链表的尾变成 list1list1 = list1->next; // list1 并没有改变,list1 迭代到list1的下一个节点}else{tail->next = list2;tail = list2;list2 = list2->next;}}// 未放置完的元素// 这里和数组的完全不一样// 链表是串联的,所以只需要把当前节点给到tail->next// 就可以全部串联if (list1){tail->next = list1;}if (list2){tail->next = list2;}// 释放哨兵位struct ListNode* ans = head->next;free(head); return ans;
}

在这里插入图片描述

1.2 思路–不强行加头结点

这道题目不使用哨兵位也能写,但是使用这种方法时,需要处理一下链表第一次合并时尾插的情况,大体思路和带哨兵位差不多,但需要注意一下细节

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if (list1 == NULL)return list2;if (list2 == NULL)return list1;struct ListNode *head, *tail;head = tail = NULL;while (list1 && list2){if (list1->val < list2->val){// 第一次合并if (tail == NULL){head = tail = list1;}else{tail->next = list1;tail = tail->next;}list1 = list1->next;}else{// 第一次合并if (tail == NULL){head = tail = list2;}else{tail->next = list2;tail = tail->next;}list2 = list2->next;}}if (list1)tail->next = list1;if (list2)tail->next = list2;return head;
}

在这里插入图片描述

2.总结:

今天我们通过两种思路分析并完成合并两个有序链表这道链表OJ题目,也更加深层次了解和使用了带哨兵位的头结点这个思路,在之后的题目中将再次出现它的使用。希望我的文章和讲解能对大家的学习提供一些帮助。

当然,本文仍有许多不足之处,欢迎各位小伙伴们随时私信交流、批评指正!我们下期见~

在这里插入图片描述

相关文章:

【链表OJ题(五)】合并两个有序链表

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;数据结构 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录链表OJ题(五)1. 合并…...

C++ Primer第五版_第三章习题答案(1~10)

文章目录练习3.1练习3.2一次读入一行一次读入一个词练习3.3练习3.4大的字符串长度大的字符串练习3.5未隔开的隔开的练习3.6练习3.7练习3.8练习3.9练习3.10练习3.1 使用恰当的using 声明重做 1.4.1节和2.6.2节的练习。 // 1.4.1 #include <iostream>using std::cin; using…...

小样本学习

机器学习就是从数据中学习&#xff0c;从而使完成任务的表现越来越好。小样本学习是具有有限监督数据的机器学习。类似的&#xff0c;其他的机器学习定义也都是在机器学习定义的基础上加上不同的限制条件衍生出来。例如&#xff0c;弱监督学习是强调在不完整、不准确、有噪声、…...

python打包成apk界面设计,python打包成安装文件

大家好&#xff0c;给大家分享一下如何将python程序打包成apk文件&#xff0c;很多人还不知道这一点。下面详细解释一下。现在让我们来看看&#xff01; 1、如何用python制作十分秒加减的apk 如何用python制作十分秒加减的apk&#xff1f;用法:. apk包放入apk文件目录,然后输入…...

pytorch转onnx踩坑日记

在深度学习模型部署时&#xff0c;从pytorch转换onnx的过程中&#xff0c;踩了一些坑。本文总结了这些踩坑记录&#xff0c;希望可以帮助其他人。 首先&#xff0c;简单说明一下pytorch转onnx的意义。在pytorch训练出一个深度学习模型后&#xff0c;需要在TensorRT或者openvin…...

极智AI | GPT4来了,ChatGPT又该升级了

欢迎关注我,获取我的更多经验分享 大家好,我是极智视界,本文介绍一下 GPT4来了,ChatGPT又该升级了,更多的是个人思考。 邀您加入我的知识星球「极智视界」,星球内有超多好玩的项目实战源码下载,链接:https://t.zsxq.com/0aiNxERDq 从 ChatGPT 发布 (2022年11月30日) 到…...

智能优化算法之灰狼优化算法(GWO)的实现(Python附源码)

文章目录一、灰狼优化算法的实现思路1、社会等级结构分级2、包围猎物3、攻击猎物4、搜索猎物二、算法步骤三、实例一、灰狼优化算法的实现思路 灰狼优化算法&#xff08;Grey Wolf Optimizer&#xff0c;简称GWO&#xff09;是由Seyedali Mirjalili等人于2014年提出的一种群智…...

leetCode热题10-15 解题代码,思路

前言 计划做一系列算法题的文章&#xff0c;因为自己这块确实比较薄弱&#xff0c;但又很重要&#xff01;写这篇文章前&#xff0c;我已经刷了一本剑指offer&#xff0c;leetcode top150道&#xff0c;牛客某题库106道 这个样子吧&#xff0c;感觉题量算是入门了吧&#xff1…...

同步辐射GISAXS和GIWAXS的原理及应用领域

同步辐射GISAXS和GIWAXS是两种常用的同步辐射X射线衍射技术&#xff0c;它们在材料科学、化学、生物学、物理学等领域中广泛应用。本文将从原理、实验方法和应用三个方面&#xff0c;对同步辐射GISAXS和GIWAXS进行描述和比较。 一、原理 GISAXS和GIWAXS都是利用X射线与样品相互…...

OpManager 进行网络性能管理

计算机网络构成了任何组织的 IT 基础架构的支柱。由于企业严重依赖基于互联网的应用程序&#xff0c;由于网络相关问题&#xff0c;最终用户不受影响非常重要。因此&#xff0c;借助网络管理解决方案监控和提高网络性能对于保持企业始终正常运行至关重要。这将确保维护服务级别…...

面试被问到向上转型和向下转型时,怎么回答?

目录 前置小知识 1、向上转型 补充&#xff1a;向上转型的三种情况 2、向下转型 使用关键字&#xff1a;instanceof 3、转型带来了什么好处 前置小知识 java中的继承&#xff0c;我们简单回顾一下 通过java中的继承机制&#xff0c;可以实现一个类继承另一个类&#xff…...

加密月解密:概述,基础篇

加密月解密&#xff1a;概述&#xff0c;基础篇 2022找工作是学历、能力和运气的超强结合体&#xff0c;遇到寒冬&#xff0c;大厂不招人&#xff0c;可能很多算法学生都得去找开发&#xff0c;测开 测开的话&#xff0c;你就得学数据库&#xff0c;sql&#xff0c;oracle&…...

DC-DC升压模块隔离高压稳压电源直流变换器12v24v48v转600V1000V1100V1500V2000V3000V

特点● 效率高达 80%● 2*2英寸标准封装● 单双电压输出● 价格低● 大于600V高压,稳压输出● 工作温度: -40℃~85℃● 阻燃封装&#xff0c;满足UL94-V0 要求● 温度特性好● 可直接焊在PCB 上应用HRB W1~25W 系列模块电源是一种DC-DC升压变换器。该模块电源的输入电压分为&am…...

pandas数据分析(三)

书接pandas数据分析&#xff08;二&#xff09; 文章目录DataFrame数据处理与分析处理超市交易数据中的异常值处理超市交易数据中的缺失值处理超市交易数据中的重复值使用数据差分查看员工业绩波动情况使用透视表与交叉表查看业绩汇总数据使用重采样技术按时间段查看员工业绩Da…...

cpu performance profiling

精彩文章分享1. android performanceAndroid 性能分析工具介绍 (qq.com)手机Android存储性能优化架构分析 (qq.com)抖音 Android 性能优化系列&#xff1a;启动优化之理论和工具篇 (qq.com)那些年&#xff0c;我们一起经历过的 Android 系统性能优化 (qq.com)Android卡顿&#…...

vue2启动项目npm run dev报错 Error: Cannot find module ‘babel-preset-es2015‘ 修改以及问题原因

报错内容如下图&#xff1a; 说找不到模块 babel-preset-es2015。 在报错之前&#xff0c;我正在修改代码&#xff0c;使用 ElementUI 的按需引入方式&#xff0c;修改了 babel.config.js 。 注意&#xff1a;vue/cli 脚手架4版本已经使用了 babel7 &#xff0c;所以项目中…...

*9 set up 注意点

1、set up 执行的时机&#xff1a;beforeCreate 之前执行一次&#xff0c;this 是 undefined 2、set up 的参数&#xff1a; props&#xff1a;值为对象&#xff0c;组件外传递属性&#xff0c;内部声明并且接收属性 context&#xff1a;上下文对象&#xff0c;其内部包含三个…...

linux目录——文件管理

个人简介&#xff1a;云计算网络运维专业人员&#xff0c;了解运维知识&#xff0c;掌握TCP/IP协议&#xff0c;每天分享网络运维知识与技能。座右铭&#xff1a;海不辞水&#xff0c;故能成其大&#xff1b;山不辞石&#xff0c;故能成其高。个人主页&#xff1a;小李会科技的…...

使用new bing简易教程

申请new bing 首先先申请new bing然后等待通过&#xff0c;如下图 申请完&#xff0c;用edge浏览器&#xff0c;若有科学方法&#xff0c;就能在右上角的聊天进行向AI提问 使用插件来进行直接访问New Bing 在edge浏览器中安装一个插件&#xff0c;地址为&#xff1a;Mod…...

idea插件分享 显著提高开发效率

idea插件 Prettier 作用&#xff1a;支持代码格式化&#xff08;java、js等&#xff09; 另外支持js内方法跳转和js中ajax请求跳转到java代码里面 下载&#xff1a;Prettier SQL Params Setter 作用&#xff1a;将日志中mapper输出preparing和paramters处理成完整可直接执行…...

为什么顶尖量化团队集体弃用Pandas?Polars 2.0清洗基准测试结果刚解禁(含12类真实业务场景压测数据)

第一章&#xff1a;Polars 2.0大规模数据清洗技巧对比评测报告Polars 2.0 在查询优化器、内存管理及并行执行策略上实现显著升级&#xff0c;尤其在处理十亿级行宽表时展现出远超 Pandas 和 DuckDB 的吞吐稳定性。本章基于真实电商日志数据集&#xff08;12.7 GB&#xff0c;8.…...

OpenClaw硬件推荐:流畅运行nanobot镜像的最低配置与性价比方案

OpenClaw硬件推荐&#xff1a;流畅运行nanobot镜像的最低配置与性价比方案 1. 为什么需要关注硬件配置&#xff1f; 去年夏天&#xff0c;我第一次尝试在笔记本上部署OpenClaw时遭遇了惨痛的失败。那台搭载i5-8250U的轻薄本在启动nanobot镜像后&#xff0c;风扇立刻像直升机一…...

光伏系统中的最大功率跟踪:滑模控制与传统方法的巧妙结合

光伏发电系统&#xff0c;滑膜控制结合扰动观察法和电导增量法&#xff0c;可更快实现 最大功率跟踪。在光伏发电系统的领域里&#xff0c;最大功率跟踪&#xff08;MPPT&#xff09;技术一直是提升发电效率的关键所在。传统的扰动观察法和电导增量法在MPPT方面各有优劣&#x…...

HTML表单回车键的隐藏陷阱:为什么你的input总在刷新页面?5种解决方案实测

HTML表单回车键的隐藏陷阱与实战解决方案 你是否曾在电商后台系统填写冗长的商品信息时&#xff0c;习惯性按下回车键换行&#xff0c;却发现整个页面突然刷新&#xff0c;刚刚输入的数据全部消失&#xff1f;这种令人抓狂的体验背后&#xff0c;隐藏着HTML表单设计中的一个经典…...

Linux小白必看!VMware虚拟机添加虚拟硬盘后必须做的5件事(附常见报错解决方案)

VMware虚拟机添加虚拟硬盘后的专业运维指南 当你为Linux系统添加新的虚拟硬盘时&#xff0c;真正的挑战往往从挂载完成后才开始。作为系统管理员&#xff0c;我们需要确保这块硬盘不仅现在能用&#xff0c;还要在未来长期稳定运行。以下是五个关键步骤&#xff0c;让你的虚拟硬…...

Au新手入门指南:从零开始掌握音频编辑基础

1. 认识Adobe Audition&#xff1a;你的第一把音频手术刀 第一次打开Adobe Audition&#xff08;简称Au&#xff09;时&#xff0c;满屏的波形图和专业术语可能会让你头皮发麻。别担心&#xff0c;这就像第一次拿手术刀的外科实习生——工具看起来很专业&#xff0c;但基础操作…...

Docker 学习之路-从入门到放弃-Jenkins:4

Jenkins 打开 ✅ 如图已经完全成功安装并初始化Jenkins了&#xff01;从图1可以确认&#xff1a;能正常访问Jenkins Web管理界面、登录成功核心功能入口&#xff08;Create a job/Manage Jenkins等&#xff09;正常显示构建执行器&#xff08;Build Executor Status&#xff09…...

LSM9DS1驱动开发指南:Arduino库深度解析与STM32移植

1. Arduino_LSM9DS1 库深度解析&#xff1a;面向嵌入式工程师的 LSM9DS1 IMU 驱动开发指南LSM9DS1 是意法半导体&#xff08;STMicroelectronics&#xff09;推出的高集成度 9 轴惯性测量单元&#xff08;IMU&#xff09;&#xff0c;内部集成了三轴加速度计、三轴陀螺仪和三轴…...

Phi-4-Reasoning-Vision多场景:科研文献插图理解+实验数据交叉验证应用

Phi-4-Reasoning-Vision多场景&#xff1a;科研文献插图理解实验数据交叉验证应用 1. 项目概述 Phi-4-Reasoning-Vision是基于微软Phi-4-reasoning-vision-15B多模态大模型开发的高性能推理工具&#xff0c;专为双卡4090环境优化。该工具严格遵循官方SYSTEM PROMPT规范&#…...

计算机毕业设计springboot社区物业管理系统 基于SpringBoot的智慧社区综合服务平台 基于SpringBoot的小区数字化运营管理系统

计算机毕业设计springboot社区物业管理系统59b07osb &#xff08;配套有源码 程序 mysql数据库 论文&#xff09; 本套源码可以在文本联xi,先看具体系统功能演示视频领取&#xff0c;可分享源码参考。 在快速城市化的今天&#xff0c;社区物业管理作为城市生活的重要组成部分&a…...