【初阶数据结构与算法】链表刷题之移除链表元素、反转链表、找中间节点、合并有序链表、链表的回文结构

在这里插入图片描述

文章目录

  • 一、移除链表元素
    • 思路一
    • 思路二
  • 二、合并两个有序链表
    • 思路:
    • 优化:
  • 三、反转链表
    • 思路一
    • 思路二
  • 四、链表的中间节点
    • 思路一
    • 思路二
  • 五、综合应用之链表的回文结构
    • 思路一:
    • 思路二:

一、移除链表元素

题目链接:https://leetcode.cn/problems/remove-linked-list-elements/

我们先来看看题目描述和第一个示例:
在这里插入图片描述
   根据题目描述我们就可以大致明白题意,就是将一个链表中的某个值的节点删除,然后返回新链表的头结点,然后题目要我们实现的函数给了我们头结点,以及要删除的数据,我们要把相应的节点删除

思路一

   首先最简单的思路就是,我们可以通过之前实现的链表的方法用上,首先使用Find方法找到对应的值,然后使用Erase方法删除,直到Find方法返回空指针结束
   由于这个方法思路比较好实现,这里就不再赘述了,可以自己尝试一下,我们的关键是更优方法的思路二

思路二

   这个题其实跟我们在刷顺序表题的时候遇见类似的,只不过之前要删除的是数组中的元素,这道题是删除链表节点,不过本质上是相同的,上次我们使用了双指针,这次我们还是可以使用双指针,顺序表刷题参考:【初阶数据结构与算法】沉浸式刷题之顺序表练习(顺序表以及双指针两种方法)
   具体思路也很像之前的那个题,题目让返回新链表的头结点,没有说必须是原链表的头结点,所以我们可以新建一个链表,如果遍历到原链表中节点的值不是题目给定的值,也就是不是我们要删除的节点,那么我们就把它尾插到新链表
   我们要注意的是,如果遇到了要插入的节点,但是新链表的头为空,我们就要让新链表的头和尾都指向这个节点,其它情况就正常尾插
   还有一个重要的地方就是,当我们把链表移动完毕之后,新链表的尾结点可能还指向原链表的节点,我们要把它置为空,题解如下:

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) 
{ListNode* newhead, *newtail;newhead = newtail = NULL;ListNode* pcur = head;while(pcur){if(pcur->val != val){if(newhead == NULL){newhead = newtail = pcur;}else{newtail->next = pcur;newtail = pcur;}}pcur = pcur->next;}if(newtail)newtail->next = NULL;return newhead;
}

在这里插入图片描述

二、合并两个有序链表

题目链接:https://leetcode.cn/problems/merge-two-sorted-lists/

我们先来看看题目的描述和第一个示例:

在这里插入图片描述
   题目给我们两个有序链表,要求我们把这两个链表合并成一个新的有序链表,然后返回它的头结点

思路:

   这个问题是不是有点似曾相识,跟我们之前的合并有序数组是一样的,我们当时的方法就是使用双指针,只是合并有序数组时是要求我们在第一个数组中进行修改,不能新建一个数组返回
   但是这道题还要简单一些,它可以新建一个链表,我们可以通过双指针遍历要合并的链表,比较两个链表中节点的大小,谁小谁就尾插到新链表,直到有一个链表走到空就停止循环
   但是我们要注意的一点是,虽然有一个链表走到空了,也就是一个链表中的节点都插入到新链表了,但是另一个链表可能还有节点,所以我们要判断一下,如果两个链表中还有一个链表不为空,那么直接将它的所有节点尾插到新链表
   还有就是做一个特殊处理,因为两个链表中可能有空链表,上面的方法就跑不通,所以我们判断一下,如果有一个链表为空,那么直接返回另一个链表,题解如下:

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}ListNode* pcur1, *pcur2;ListNode* newhead, *newtail;pcur1 = list1;pcur2 = list2;newhead = newtail = NULL;while(pcur1 && pcur2){if(pcur1->val < pcur2->val){if(newhead == NULL){newhead = newtail = pcur1;}else{newtail->next = pcur1;newtail = pcur1;}pcur1 = pcur1->next;}else{if(newhead == NULL){newhead = newtail = pcur2;}else{newtail->next = pcur2;newtail = pcur2;}pcur2 = pcur2->next;}}if(pcur1){newtail->next = pcur1;}if(pcur2){newtail->next = pcur2;}return newhead;
}

在这里插入图片描述

优化:

   上面的代码是一种题解,但是我们可以发现,这个代码写起来有点麻烦,有一些重复的动作,就是在每次插入之前,我们要判断链表是否为空,如果为空要让新链表的头和尾都指向要插入的节点
   那我们能不能让代码更加简洁一点呢?就是不必每次插入节点前都判断链表是否为空,这里就可以用上我们之前学过的带头的概念,我们申请一个不保存数据的哨兵位当作链表默认的头
   这样我们的新链表默认就有了一个节点,不为空了,可以直接在哨兵位后面尾插节点,不用判断链表是否为空,最后返回时就返回哨兵位的下一个节点就可以了,它就是我们新链表中保存数据的头节点
   不过由于我们的哨兵位是通过malloc来的,所以最后代码结束时不要记得把它释放掉,以免造成内存泄漏,如下:

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}ListNode* pcur1, *pcur2;pcur1 = list1, pcur2 = list2;ListNode* newhead, *newtail;newhead = newtail = (ListNode*)malloc(sizeof(ListNode));while(pcur1 && pcur2){if(pcur1-> val < pcur2->val){newtail->next = pcur1;newtail = pcur1;pcur1 = pcur1->next;}else{newtail->next = pcur2;newtail = pcur2;pcur2 = pcur2->next;}}if(pcur1){newtail->next = pcur1;}if(pcur2){newtail->next = pcur2;}ListNode* ret = newhead->next;free(newhead);newhead = NULL;return ret;
}

在这里插入图片描述

三、反转链表

题目链接:https://leetcode.cn/problems/reverse-linked-list/

我们来看看题目描述和第一个示例:
在这里插入图片描述
   题目要求我们将给出的链表反转,就是改变指针的指向,让原本的尾节点变成头,让原本的头结点变成尾

思路一

   思路一还是很简单,就是我们创建一个新链表,遍历原链表,拿原链表中的节点头插到新链表就可以了,如图:
在这里插入图片描述
在这里插入图片描述
   有了上图的分析,实现就很简单了,只需要一个头插方法,我们之前讲过,这里就不再赘述了,可以自己试试,我们重点介绍思路二

思路二

   思路二比较难想出来,但是确实非常快,因为它是对原链表的节点的指针指向进行修改,所以很快,并且不会消耗什么空间,思路如图:
在这里插入图片描述
在这里插入图片描述
   有了上面的思路我们就可以来写代码了,但是我们要注意一个点,就是如果题目直接给出一个空链表让我们反转,那么我们对它解引用就会出错,所以我们特殊处理一下,如果链表为空就直接返回,空链表反转还是空链表,题解如下:

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) 
{if(head == NULL){return head;}ListNode* n1, *n2, *n3;n1 = NULL;n2 = head;n3 = head->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3)n3 = n3->next;}return n1;
}

在这里插入图片描述

四、链表的中间节点

题目链接:https://leetcode.cn/problems/middle-of-the-linked-list/

我们来看看题目描述和两个示例,如下:
在这里插入图片描述
   它的要求就是让我们返回链表的中间节点,如果是偶数个节点,那么就有两个中间节点,则返回后一个节点

思路一

   我们首先能想到的思路就是,先遍历整个链表,看看链表一共有多少个节点,然后让它除以2,最后再次循环遍历链表就可以找到中间节点,这个题很简单,我们直接给出题解,如下:

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) 
{int count = 0;ListNode* pcur = head;while(pcur){count++;pcur = pcur->next;}count /= 2;pcur = head;while(count--){pcur = pcur->next;}return pcur;
}

在这里插入图片描述

   虽然这个方法看起来已经很简单了,但是始终都是执行了两次循环,有没有更简单的方法呢?接下来我们来看看思路二

思路二

   思路二的方法很绝妙,简单又快捷,就是使用快慢指针的算法,快慢指针默认都指向头结点,慢指针一次走一步,快指针一次走两步,那么等快指针走到空的时候,慢指针指向的节点就是中间节点
   为什么呢?因为快指针每次走的距离都是慢指针的2倍,最后统计一共走的距离时,快指针走的总距离也是慢指针的2倍,而快指针走到了空,也就说明走到了链表尾,那么此时慢指针就是它的一半,刚好指向中间节点,题解如下:

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) 
{ListNode* slow, *fast;slow = fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

在这里插入图片描述

五、综合应用之链表的回文结构

题目链接:https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa

我们先来看看题目描述和它的第一个示例:
在这里插入图片描述
   题目要求我们判断给出的链表是否是一个回文结构,也就是是否前后对称,这道题就可以用上我们之前做题写出的代码,具体后面再说,我们先解决一个事情
   就是这个题目没有提供C语言的选项,那我们就选择C++来做,C++是兼容C语言的,主要是我们要知道在哪里写代码,如图:
在这里插入图片描述

   这是C++中的类,但是不影响我们做题,我们只需要知道我们把代码写在哪里,在题目中也有提示,把代码写在紫色大括号内即可,其它的可以不管,还有一个就是,C++对结构体做了优化,可以在使用结构体时不必加上struct

思路一:

   虽然判断链表是否是回文结构很难,但是我们可以把链表中的数据存放到数组中,判断数组是否是回文结构,这个就比较简单了
   由于链表两边的数据是对称的,所以我们定义一个left和right分别指向数组的头和尾,然后对比它们的值,如果不同直接返回假,否则的话就一直让它们往中间走,直到left不再小于right
   在循环过程中,一旦left所在位置的值和right所在位置的值不相同,就说明并不对称,也就不是回文结构,返回假,一旦循环结束,说明左右对称,就是回文结构,直接返回真
   并且我们注意到,虽然题目要求空间复杂度为O(1),但是同时又给出了链表的最大节点个数不超过900,那定义一个901个元素大小的数组时间复杂度还是O(1),因为它始终还是常数个空间,如下:

class PalindromeList {
public:bool chkPalindrome(ListNode* A) {int arr[901] = { 0 };ListNode* pcur = A;int i = 0;while(pcur){arr[i++] = pcur->val;pcur = pcur->next;}int left = 0, right = i-1;while(left < right){if(arr[left] != arr[right]){return false;}left++, right--;}return true;}
};

在这里插入图片描述
   最后就是,这个方法虽然很简单,但是只适合给出了链表节点大小的题目,如果遇到没有给出链表节点大小的题目就会导致时间复杂度变成O(N),导致不符合要求,所以我们再介绍一个方法

思路二:

   这个思路可以帮我们复习上面做过的题,让我们能够灵活运用知识,具体思路就是,我们首先通过找中间节点的函数找到链表中间节点,然后从中间节点开始,将后面的节点反转,形成一个新链表,然后再和原链表进行比较即可,如图:
在这里插入图片描述
   找中间节点的函数和反转链表的函数可以从我们之前做过的题里面拿过来用,当然也可以自己根据这个逻辑把中间的代码实现,这里我就直接把之前写过的函数直接拿过来用,如下:

class PalindromeList {public:struct ListNode* reverseList(struct ListNode* head) {if (head == NULL) {return head;}ListNode* n1, *n2, *n3;n1 = NULL;n2 = head;n3 = head->next;while (n2) {n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;}struct ListNode* middleNode(struct ListNode* head) {ListNode* slow, *fast;slow = fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}return slow;}bool chkPalindrome(ListNode* A) {if(A == NULL){return true;}ListNode* mid = middleNode(A);ListNode* newlist = reverseList(mid);ListNode* pcur1, *pcur2;pcur1 = A, pcur2 = newlist;while(pcur2){if(pcur1->val != pcur2->val){return false;}pcur1 = pcur1->next;pcur2 = pcur2->next;}return true;}
};

在这里插入图片描述

   那么今天的链表刷题训练就到这里结束啦,有什么不懂欢迎提出,我们下一篇文章还是刷题,之后我们会讲栈和队列的实现,敬请期待
   bye~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/470642.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

POI实现根据PPTX模板渲染PPT

目录 1、前言 2、了解pptx文件结构 3、POI组件 3.1、引入依赖 3.2、常见的类 3.3、实现原理 3.4、关键代码片段 3.4.1、获取ppt实例 3.4.2、获取每页幻灯片 3.4.3、循环遍历幻灯片处理 3.4.3.1、文本 3.4.3.2、饼图 3.4.3.3、柱状图 3.4.3.4、表格 3.4.3.5、本地…

计算机毕业设计Python+Neo4j知识图谱医疗问答系统 大模型 机器学习 深度学习 人工智能 大数据毕业设计 Python爬虫 Python毕业设计

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…

【机器学习】机器学习中用到的高等数学知识-2.概率论与统计 (Probability and Statistics)

概率分布&#xff1a;理解数据的分布特征&#xff08;如正态分布、伯努利分布、均匀分布等&#xff09;。期望和方差&#xff1a;描述随机变量的中心位置和离散程度。贝叶斯定理&#xff1a;用于推断和分类中的后验概率计算。假设检验&#xff1a;评估模型的性能和数据显著性。…

Scala入门基础(17.1)Set集习题

一.选择题 二.实训 图书馆书籍管理系统相关的练习。内容要求&#xff1a; 1.创建一个可变 Set&#xff0c;用于存储图书馆中的书籍信息 &#xff08;假设书籍信息用字符串表示&#xff0c;如“Java编程思想”“Scala实战”等&#xff09; 2.添加两本新的书籍到图书馆集合中&a…

移动端【01】面试系统的MVVM重构实践

基于MVVM的移动端面试系统重构实践&#xff1a;模块化设计与实现 一、项目背景 面试记录表系统在经过一年多的迭代后&#xff0c;代码质量问题日益突出。View和ViewModel代码均超过3000行&#xff0c;组件引用超过1000个&#xff0c;亟需进行架构重构。本文将详细介绍基于MVV…

Springboot 启动端口占用如何解决

Springboot 启动端口占用如何解决 1、报错信息如下 *************************** APPLICATION FAILED TO START ***************************Description:Web server failed to start. Port 9010 was already in use.Action:Identify and stop the process thats listening o…

基于Python+Django+Vue3+MySQL实现的前后端分类的商场车辆管理系统

项目名称&#xff1a;基于PythonDjangoVue3MySQL实现的前后端分离商场车辆管理系统 技术栈 开发工具&#xff1a;PyCharm、Visual Studio Code (VSCode)运行环境&#xff1a;Python 3.10、MySQL 8.0、Node.js 18技术框架&#xff1a;Django 5、Vue 3.4、Ant-Design-Vue 4.12 …

ML 系列: 第 23 节 — 离散概率分布 (多项式分布)

目录 一、说明 二、多项式分布公式 2.1 多项式分布的解释 2.2 示例 2.3 特殊情况&#xff1a;二项分布 2.4 期望值 &#xff08;Mean&#xff09; 2.5 方差 三、总结 3.1 python示例 一、说明 伯努利分布对这样一种情况进行建模&#xff1a;随机变量可以采用两个可能的值&#…

Openstack7--安装消息队列服务RabbitMQ

只需要在控制节点安装 安装RabbitMQ yum -y install rabbitmq-server 启动RabbitMQ并设置开机自启 systemctl start rabbitmq-server;systemctl enable rabbitmq-server 创建 rabbitmq 用户 并设置密码为 000000 rabbitmqctl add_user rabbitmq 000000 如果你不慎创错了…

图像处理实验二(Image Understanding and Basic Processing)

图像理解&#xff08;Image Understanding&#xff09;和基本图像处理&#xff08;Basic Image Processing&#xff09;是计算机视觉领域的重要组成部分。它们涉及从图像中提取有用信息、分析图像内容、并对其进行处理以达到特定目的。图像理解通常包括识别、分类和解释图像中的…

第74期 | GPTSecurity周报

GPTSecurity是一个涵盖了前沿学术研究和实践经验分享的社区&#xff0c;集成了生成预训练Transformer&#xff08;GPT&#xff09;、人工智能生成内容&#xff08;AIGC&#xff09;以及大语言模型&#xff08;LLM&#xff09;等安全领域应用的知识。在这里&#xff0c;您可以找…

Kafka - 启用安全通信和认证机制_SSL + SASL

文章目录 官方资料概述制作kakfa证书1.1 openssl 生成CA1.2 生成server端秘钥对以及证书仓库1.3 CA 签名证书1.4 服务端秘钥库导入签名证书以及CA根证书1.5 生成服务端信任库并导入CA根数据1.6 生成客户端信任库并导入CA根证书 2 配置zookeeper SASL认证2.1 编写zk_server_jass…

除了 Postman,还有什么好用的 API 调试工具吗

尽管 Postman 拥有团队协作等实用特性&#xff0c;其免费版提供的功能相对有限&#xff0c;而付费版的定价可能对小团队或个人开发者而言显得偏高。此外&#xff0c;Postman 的访问速度有时较慢&#xff0c;这可能严重影响使用体验。 鉴于这些限制&#xff0c;Apifox 成为了一…

matlab建模入门指导

本文以水池中鸡蛋温度随时间的变化为切入点&#xff0c;对其进行数学建模并进行MATLAB求解&#xff0c;以更为通俗地进行数学建模问题入门指导。 一、问题简述 一个煮熟的鸡蛋有98摄氏度&#xff0c;将它放在18摄氏度的水池中&#xff0c;五分钟后鸡蛋的温度为38摄氏度&#x…

【C#设计模式(8)——过滤器模式(Adapter Pattern)】

前言 滤液器模式可以很方便地实现对一个列表中的元素进行过滤的功能&#xff0c;能方便地修改滤器的现实&#xff0c;符合开闭原则。 代码 //过滤接口public interface IFilter{List<RefuseSorting> Filter(List<RefuseSorting> refuseList);}//垃圾分类public cla…

事件循环 -- 资源总结(浏览器进程模型、事件循环机制、练习题)

!!! 理解学习&#xff0c;有问题/补充欢迎指出&#xff0c;随时改正 !!! 事件循环 一、进程与线程二、浏览器进程模型三、为什么会存在事件循环机制四、事件循环机制五、代码场景模拟事件循环机制六、练习题(明天补充...) 一、进程与线程 进程&#xff08;Process&#xff09;…

九州未来再度入选2024边缘计算TOP100

随着数智化转型的浪潮不断高涨&#xff0c;边缘计算作为推动各行业智能化升级的重要基石&#xff0c;正在成为支持万物智能化的关键点。近日&#xff0c;德本咨询(DBC)联合《互联网周刊》(CIW)与中国社会科学院信息化研究中心(CIS)&#xff0c;共同发布《2024边缘计算TOP100》榜…

使用 start-local 脚本在本地运行 Elasticsearch

警告&#xff1a;请勿将这些说明用于生产部署 本页上的说明仅适用于本地开发。请勿将此配置用于生产部署&#xff0c;因为它不安全。请参阅部署选项以获取生产部署选项列表。 使用 start-local 脚本在 Docker 中快速设置 Elasticsearch 和 Kibana 以进行本地开发或测试。 此设…

【Linux】TCP原理

tcp协议段格式 源/目的端口号: 表示数据是从哪个进程来, 到哪个进程去;4 位 TCP 报头长度: 表示该 TCP 头部有多少个 32 位 bit(有多少个 4 字节); 所以TCP 头部最大长度是 15 * 4 6016 位校验和: 发送端填充, CRC 校验. 接收端校验不通过, 则认为数据有问题. 此处的检验和不光…

阿里巴巴通义灵码推出Lingma SWE-GPT:开源模型的性能新标杆

阿里巴巴通义灵码团队最近开源了一款名为Lingma SWE-GPT的自动化软件改进模型。这一模型在软件工程领域的应用中表现出色&#xff0c;首次在SWE-bench基准测试中达到了30.20%的解决率&#xff0c;这一成绩比Llama 3.1 405B高出22.76%&#xff0c;标志着开源模型在这一领域的重大…