合并两个有序链表(精美图示详解哦)
全文目录
- 引言
- 合并两个有序链表
- 题目描述
- 方法一:将第二个链表合并到第一个
- 思路
- 实现
- 方法二:尾插到哨兵位的头节点
- 思路
- 实现
- 总结
引言
在前面两篇文章中,我们介绍了几道链表的习题:反转链表、链表的中间结点、链表的倒数第k个结点:
戳我看反转链表详解哦
戳我看链表的中间结点与链表的倒数第k个结点详解哦
本篇文章中,将继续介绍关于链表的题目:合并两个有序链表:
合并两个有序链表OJ链接
合并两个有序链表
题目描述
这道题要求我们将两个有序链表合并为一个链表,并返回合并后链表的首结点地址。
参数为两个链表的首结点地址,两个链表均为非递减排序,即链表中的数据为递增或相等序列。结构体变量与主函数部分已经定义,我们只需要实现接口即可。
在之前我们做过合并两个有序数组的题目,我们可以使用双指针的方法,将一数组中的元素按照顺序插入到另一数组中:即从后向前遍历两个数组,将较大的元素插入到数组的末尾。
对于链表的合并,我们也可以借鉴这种方法:
方法一:将第二个链表合并到第一个
思路
我们可以创建用两个指针,从前向后分别遍历两个链表:
若list1中指针指向的结点的数据大于list2中指针指向的,将list2中的元素插入到list1中元素的前面,然后list1中的指针位置不变,list2中的指针向后移动一个结点;若list1中指针指向的结点小于list2中的,list1中的指针向前移动一个结点。
若list1中的指针遍历到末尾,则说明list2中还有结点没有插入到list2中,且这些结点的数据大于list1中的,所以直接将这个指针插入到list1末尾即可。
但是,这样的方法会有些复杂,尤其是在插入的时候的情况较麻烦,这一点大家在后面的实现中可以体会到。
实现
为了使代码更简洁,我们可以对结构体名称重命名:
typedef struct ListNode ListNode;
要实现这个算法,我们首先需要两个指针变量cur1与cur2,将它们分别初始化为两个链表的首结点地址:
ListNode* cur1 = list1;
ListNode* cur2 = list2;
并且,当我们要将cur2指向的结点插入到cur1指向的结点前时,需要一个指向cur1前面的结点的地址用来辅助,我们将这个指针初始化为NULL:
ListNode* beforecur1 = NULL;
首先,我们需要判断链表2是否为空链表,通过判断cur2的值即可:当cur2的值为NULL时,直接返回第一个链表的首结点地址list1;
然后,while循环,循环需要cur1与cur2都不为空:
在循环中,判断cur1->val的与cur2->val的大小:
若cur1->val大于cur2->val,有两种情况:
若cur1是链表的第一个结点(即beforecur的值为NULL没有被改变),我们就需要将cur2指向的结点头插到list1中。即先将list2赋值为cur2->next,将其向后移动一个结点;然后将cur2->next赋值为list1,即原来第一个链表的首结点地址;然后将beforecur1赋值为cur2,即将其移动到cur1的前一个结点处;最后,将list1改为cur2,即现链表1的首结点,将cur2改为list2,即cur2在链表2中向后移动一个结点。
若cur1不是链表的第一个结点,我们就将cur2指向的结点插入到cur1指向结点的前面。即先将list2赋值为cur2->next,将其向后移动一个结点;然后将beforecur1->next改为cur2,即让cur1前面的结点连接上cur2;然后将beforecur1赋值为cur2,即将其移动到cur1的前一个结点处;然后,将cur2->next改为cur1,即让cur2连接上cur1.最后,将cur2改为list2,即cur2在链表2中向后移动一个结点。
若cur1->val小于等于cur2->val,将cur1向后移动一个结点即可:
首先将beforecur1改为cur1,即向后移动一个结点。然后将cur1改为cur1->next即将cur1向后一动一个结点即可:
typedef struct ListNode ListNode;struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{ListNode* cur1 = list1;ListNode* beforecur1 = NULL;ListNode* cur2 = list2;if (cur2 == NULL){return list1;}while (cur1 && cur2){if (cur1->val > cur2->val){if (beforecur1 == NULL){list2 = cur2->next;cur2->next = list1;beforecur1 = cur2;list1 = cur2;cur2 = list2;}else{list2 = cur2->next;beforecur1->next = cur2;beforecur1 = cur2;cur2->next = cur1;cur2 = list2;}}else{beforecur1 = cur1;cur1 = cur1->next;}}if (cur2){if (beforecur1 == NULL){list1 = cur2;}else{beforecur1->next = cur2;}}return list1;
}
方法二:尾插到哨兵位的头节点
思路
我们可以直接创建一个哨兵位的头结点,然后将cur1与cur2中的较大值尾插到该哨兵位的头节点后。这样,就可以避免我们在cur1前插入结点时的复杂情况:
不需要判断cur1是否为第一个结点,并且尾插要比在前面插入更加方便。
实现
为实现这个算法,在需要结构体指针cur1与cur2之外,我们还需要两个指针,用来表示新的链表的首结点地址与尾结点地址:
ListNode* tail = NULL;
ListNode* guard = NULL;
需要说明的是,哨兵位的头节点是放在链表的起始位置,可以使在链表中插入第一个结点时更方便。是不计入链表的数据的。
我们可以动态开辟这块空间:
guard = tail = (ListNode*)malloc(sizeof(ListNode));
当然,需要if判断是否开辟成功:
if (guard == NULL){perror("malloc");}
接下来可以直接进入循环,需要cur1与cur2均不为空:
在循环中,判断cur1->val的与cur2->val的大小:
若cur1->val大于cur2->val:
将tail->next改为cur2,即将哨兵结点的末尾与cur2连接起来。然后将tail改为tail->next,即使其依旧指向新链表的末尾。然后将cur2改为cur2->next,即cur2向后移动一个结点。
若cur1->val小于等于cur2->val:
将tail->next改为cur1,即将哨兵结点的末尾与cur1连接起来。然后将tail改为tail->next,即使其依旧指向新链表的末尾。然后将cur1为cur1->next,即cur1向后移动一个结点。
在结束循环后,若cur2不为空,说明链表2还剩余结点,且大于其他的任何数据,将其接在新链表的末尾即可;
cur1不为空同理,将其接到新节点末尾即可:
最后,需要注意的是,guard指向的哨兵位的头节点是动态开辟的空间,所以需要free释放。但是由于释放后就不能返回值,所以先用一个ret指针记录guard->next的值,等释放guard指向的空间后,返回ret即可:
typedef struct ListNode ListNode;struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{ListNode* cur1 = list1;ListNode* cur2 = list2;ListNode* tail = NULL;ListNode* guard = NULL;guard = tail = (ListNode*)malloc(sizeof(ListNode));if (guard == NULL){perror("malloc");}while (cur1 && cur2){if (cur1->val > cur2->val){tail->next = cur2;tail = tail->next;cur2 = cur2->next;}else{tail->next = cur1;tail = tail->next;cur1 = cur1->next;}}if (cur2){tail->next = cur2; }else{tail->next = cur1;}ListNode* ret = guard->next;free(guard);return ret;
}
总结
到此,关于合并两个有序链表的两种解法已经介绍完了,第二种方法显然是简单很多的。当然会有其他的算法解决,欢迎大家在评论区讨论
后续可能还会有几道链表的相关题目,欢迎大家持续关注哦
如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题,欢迎大家在评论区提出
如果本文对你有帮助,希望一键三连哦
希望与大家共同进步哦
相关文章:

合并两个有序链表(精美图示详解哦)
全文目录引言合并两个有序链表题目描述方法一:将第二个链表合并到第一个思路实现方法二:尾插到哨兵位的头节点思路实现总结引言 在前面两篇文章中,我们介绍了几道链表的习题:反转链表、链表的中间结点、链表的倒数第k个结点&…...

33 JSON操作
目录 一、介绍 二、JSON的特点 三、JSON语法 1、json中的数据类型 四、JSON文件的定义 五、读取JSON文件 1、读取json文件的两种方式 (1)read、write (2)json.load 2、使用json.load读取json文件的步骤 3、练习读取json文件 六、练…...
三八妇女节快乐----IT女神活动随笔
献丑了,一首小小散文诗,请大家轻喷 O(≧口≦)O 我的答案 天下芸芸众生,好似夜幕漫天繁星。 与你相识,只是偶然。 简单的一个招呼,于是开始了一段故事。 我们或是诉说,或是分享; 我们彼此倾听&…...

【PSO-PID】使用粒子群算法整定PID参数控制起动机入口压力值
最近在学优化算法,接触到了经典寻优算法之粒子群PSO,然后就想使用PSO算法来调节PID参数,在试验成功之后将此控制算法应用到了空气起动系统上,同时与之前的控制器进行对比看看哪种控制效果最好。 0 引言 PID参数整定主要有两种&…...

当代数据分析指南:激发商业洞见的七个方法(上)
如果说眼下的发生的事能证明什么,那就是基于实时可信的数据分析正在变得越来越重要。但是要是想要在需要的时候准确地获取中肯的洞察,我们所需要的可不只是漂亮的可视化。 如何让你的员工都有能力和机会都做出最好的决策,不管这个决策会有多…...

javaWeb核心02-JSP、EL、JSTL、MVC
文章目录JSP1,JSP 概述2,JSP 快速入门2.1 搭建环境2.2 导入 JSP 依赖2.3 创建 jsp 页面2.4 编写代码2.5 测试3,JSP 原理4,JSP 脚本4.1 JSP 脚本分类4.2 案例4.2.1 需求4.2.2 实现4.2.3 成品代码4.2.4 测试4.3 JSP 缺点5࿰…...
spring-boot+mybatis-plus连接Oracle数据库,及查询相关数据
配置java 略(这里我用的是jdk1.8) 配置maven 环境变量: M2_HOME:D:\LJ\software\java\maven\apache-maven-3.6.3 Path:%M2_HOME%\bin 仓库/jdk/镜像云设置(./config/sitting) 仓库 <localRepository> D:/…...

电商使用CRM系统有什么好处,如何选择
数据显示,使用电商CRM客户管理系统后,企业销售额提高了87%,客户满意度提高了74%,业务效率提高了73%。要在竞争激烈的电商市场取得成功,与目标受众的有效沟通是有效的方法。下面说说什么是电商CRM系统?电商C…...

Nacos2.2.0多数据源适配oracle12C-修改Nacos源码
从2.2.0版本开始,可通过SPI机制注入多数据源实现插件,并在引入对应数据源实现后,便可在Nacos启动时通过读取application.properties配置文件中spring.datasource.platform配置项选择加载对应多数据源插件.本文档详细介绍一个多数据源插件如何实现以及如何使其生效。 文章目录一…...

第十四届蓝桥杯三月真题刷题训练——第 5 天
目录 题目1:数的分解 题目描述 运行限制 代码: 题目2:猜生日 题目描述 运行限制 代码: 题目3:成绩分析 题目描述 输入描述 输出描述 输入输出样例 运行限制 代码: 题目4:最大和…...
大数据框架之Hive:第3章 DDL(Data Definition Language)数据定义
第3章 DDL(Data Definition Language)数据定义 3.1 数据库(database) 3.1.1 创建数据库 1)语法 CREATE DATABASE [IF NOT EXISTS] database_name [COMMENT database_comment] [LOCATION hdfs_path] [WITH DBPROPER…...
概率论小课堂:统计学是大数据方法的基础
文章目录 引言I 统计学1.1 统计学的内容1.2 统计学的目的II 用好数据的五个步骤2.1 设立研究目标2.2 设计实验,选取数据。2.3 根据实验方案进行统计和实验,分析方差。2.4 通过分析进一步了解数据,提出新假说。2.5 使用研究结果III 数据没用好的原因3.1 霍桑效应3.2 数据的稀…...
监控集群概念讲解
监控概述 1、监控的重要性 监控是运维日常的重要工作之一; 监控是有多重要? 监控可以帮助运维监控服务器的状态;要及时解决; 如果淘宝、腾讯宕机了1个小时? 损失是无法估量的; 服务器是否故障、宕不…...

如何通过DAS连接GaussDB
文章目录1 实验介绍2 实验目的3 配置DAS服务4 SQL使用入门1 实验介绍 本实验主要描述如何通过华为云数据管理服务 (Data Admin Service,简称DAS) 来连接华为云GaussDB数据库实例,DAS是一款专业的简化数据库管理工具,提供优质的可视化操作界面…...

支持在局域网使用的项目管理系统有哪些?5款软件对比
一、选择私有部署的原因以及该方案的优点有很多可能的原因导致人们更倾向于使用私有部署的企业管理软件,其中一些原因可能包括:1.数据安全性要求:一些企业管理软件包含敏感的商业数据和隐私信息,为了保护这些信息不被未经授权的第…...

Linux CentOS7 MySQL 5.7安装
准备工作 //创建目录 mkdir /opt/mysql //跳转目录 cd /opt/mysql下载MySQL 请耐心等待,也可以在Windows下载以后上传到 /opt/mysql目录 wget http://dev.mysql.com/get/mysql-5.7.26-1.el7.x86_64.rpm-bundle.tar解压 tar -xvf mysql-5.7.26-1.el7.x86_64.rpm-b…...
Kubernetes学习(四)控制器
ReplicaSet ReplicaSet的目的是维护一组在任何时候都处于运行状态的Pod副本的稳定集合。因此,它通常用来保证给定数量的、完全相同的Pod的可用性。 ReplicaSet的工作原理 ReplicaSet是通过一组字段来定义的,包括一个用来识别可获得的pod的集合的选择符…...
vue组件间通信的几个方法
一,props属性传递数据 适用场景:父组件传递数据给子组件 子组件设置props属性,定义接收父组件传递过来的参数 父组件在使用子组件标签中通过字面量来传递值 Children.vue props:{ // 字符串形式 name:String // 接收的类型参数 // 对象…...
商品价格区间设置与排序--课后程序(Python程序开发案例教程-黑马程序员编著-第4章-课后作业)
实例2:商品价格区间设置与排序 在网上购物时,面对琳琅满目的商品,我们应该如何快速选择适合自己的商品呢?为了能够让用户快速地定位到适合自己的商品,每个电商购物平台都提供价格排序与设置价格区间功能。假设现在某平…...
mybatis中sqlSession的使用
文章目录sqlsession的使用依赖jdbc.propertiesmysql-config.xml配置逆向工程创建sqlSessionsqlsession的使用 在最开始我们使用jdbcUtil的方式进行硬编码,sql字符串写的很难受,使用mybatis可以解决这个问题,它提供了数据库与实体类的关系映射…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...

Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

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

04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...

排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...
C++.OpenGL (20/64)混合(Blending)
混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...

Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...