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

合并两个有序链表(精美图示详解哦)

全文目录

  • 引言
  • 合并两个有序链表
    • 题目描述
    • 方法一:将第二个链表合并到第一个
      • 思路
      • 实现
    • 方法二:尾插到哨兵位的头节点
      • 思路
      • 实现
  • 总结

引言

在前面两篇文章中,我们介绍了几道链表的习题:反转链表、链表的中间结点、链表的倒数第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&#xff0…...

spring-boot+mybatis-plus连接Oracle数据库,及查询相关数据

配置java 略&#xff08;这里我用的是jdk1.8&#xff09; 配置maven 环境变量&#xff1a; M2_HOME&#xff1a;D:\LJ\software\java\maven\apache-maven-3.6.3 Path&#xff1a;%M2_HOME%\bin 仓库/jdk/镜像云设置(./config/sitting) 仓库 <localRepository> D:/…...

电商使用CRM系统有什么好处,如何选择

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

Nacos2.2.0多数据源适配oracle12C-修改Nacos源码

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

第十四届蓝桥杯三月真题刷题训练——第 5 天

目录 题目1&#xff1a;数的分解 题目描述 运行限制 代码&#xff1a; 题目2&#xff1a;猜生日 题目描述 运行限制 代码&#xff1a; 题目3&#xff1a;成绩分析 题目描述 输入描述 输出描述 输入输出样例 运行限制 代码&#xff1a; 题目4&#xff1a;最大和…...

大数据框架之Hive:第3章 DDL(Data Definition Language)数据定义

第3章 DDL&#xff08;Data Definition Language&#xff09;数据定义 3.1 数据库&#xff08;database&#xff09; 3.1.1 创建数据库 1&#xff09;语法 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、监控的重要性 监控是运维日常的重要工作之一&#xff1b; 监控是有多重要&#xff1f; 监控可以帮助运维监控服务器的状态&#xff1b;要及时解决&#xff1b; 如果淘宝、腾讯宕机了1个小时&#xff1f; 损失是无法估量的&#xff1b; 服务器是否故障、宕不…...

如何通过DAS连接GaussDB

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

支持在局域网使用的项目管理系统有哪些?5款软件对比

一、选择私有部署的原因以及该方案的优点有很多可能的原因导致人们更倾向于使用私有部署的企业管理软件&#xff0c;其中一些原因可能包括&#xff1a;1.数据安全性要求&#xff1a;一些企业管理软件包含敏感的商业数据和隐私信息&#xff0c;为了保护这些信息不被未经授权的第…...

Linux CentOS7 MySQL 5.7安装

准备工作 //创建目录 mkdir /opt/mysql //跳转目录 cd /opt/mysql下载MySQL 请耐心等待&#xff0c;也可以在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副本的稳定集合。因此&#xff0c;它通常用来保证给定数量的、完全相同的Pod的可用性。 ReplicaSet的工作原理 ReplicaSet是通过一组字段来定义的&#xff0c;包括一个用来识别可获得的pod的集合的选择符…...

vue组件间通信的几个方法

一&#xff0c;props属性传递数据 适用场景&#xff1a;父组件传递数据给子组件 子组件设置props属性&#xff0c;定义接收父组件传递过来的参数 父组件在使用子组件标签中通过字面量来传递值 Children.vue props:{ // 字符串形式 name:String // 接收的类型参数 // 对象…...

商品价格区间设置与排序--课后程序(Python程序开发案例教程-黑马程序员编著-第4章-课后作业)

实例2&#xff1a;商品价格区间设置与排序 在网上购物时&#xff0c;面对琳琅满目的商品&#xff0c;我们应该如何快速选择适合自己的商品呢&#xff1f;为了能够让用户快速地定位到适合自己的商品&#xff0c;每个电商购物平台都提供价格排序与设置价格区间功能。假设现在某平…...

mybatis中sqlSession的使用

文章目录sqlsession的使用依赖jdbc.propertiesmysql-config.xml配置逆向工程创建sqlSessionsqlsession的使用 在最开始我们使用jdbcUtil的方式进行硬编码&#xff0c;sql字符串写的很难受&#xff0c;使用mybatis可以解决这个问题&#xff0c;它提供了数据库与实体类的关系映射…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...