单链表习题——快慢指针类习题详解!(2)

前言:

  正如标题所言,小编今天要讲述快慢指针的相关习题,可能有些读者朋友会有些疑问了,这快慢指针是个什么东西?不要着急,下面紧跟小编的步伐,开启我们今天的快慢指针之旅!

目录:

1.快慢指针是什么?

2.快慢指针习题详解

2.1.链表的中间结点

2.2.环形链表

2.3.链表的回文结构

2.4.环形链表Ⅱ

正文:

1.快慢指针是什么

  顾名思义,快慢指针就是一个快指针和一个慢指针,一个指针向后走到速度快(一般我们在使使用快指针的时候让它向后走两步),所以被称之为快指针,一个指针向后走的速度慢(一般我们在使用满指针的时候让它走一步),所以被称之为慢指针,这两个指针对于我们在处理一些习题的时候有很大的作用,下面紧跟小编的步伐,开始进入今天的快慢指针之旅~

2.快慢指针习题详解

2.1.链表的中间结点 

  老规矩,先给上习题的链接:876. 链表的中间结点 - 力扣(LeetCode)

   小编相信,很多读者朋友拿到这个题目的时候感觉是有点懵的(大佬除外),小编在当初看到这个题的时候也是感觉脑子有些懵,如果这个题目是数组的化,那么就会显的很简单,问题是这个不是数组,而是单链表,我们不可以用除法直接寻找单链表,我们需要遍历单链表来找到中间节点,小编那时候想到过一个解法,就是把单链表的每一个元素都放入到一个新开辟的数组中,然后我们通过数组找到中间节点里面存的数据,然后通过数据找到中间节点,这个做法虽然是可行的,但是在这里就显得很冗余,写代码,我们就要越简单越好,于是小编在之后学到了一个解法,那么就是用快慢指针来寻找中间节点,下面小编讲述下如何通过快慢指针找到中间结点:

  首先,我们需要用到两个指针,我们可以先让这两个指针指向头节点,之后我们需要进入循环来找中间结点,至于循环的条件我们稍后再说,我们让满指针往后走一步,快指针往后走两步,我们可以发现,当快指针的下一个结点走向空或者自己本身就是空的时候,此时慢指针指向的就是中间结点,所以我们知道了循环的条件就是快指针本身或者它的下一个结点不为空,下面小编通过图文帮助读者朋友们进行更好的了解:

  先放置好指针:

   开始往后走,short1往后走一步,long1往后走两步:

  此时long1的下一个结点还不是空,继续重复上述步骤:

  此时,long1的下一个结点是空,所以此时停止循环了,我们可以发现此时short1正好就是中间结点,此时我们返回short1就好了,此时这个题目我们已经宣告完成了,不过现在肯定有不少读者朋友好奇为什么快慢指针可以这么找到中间结点,小编下面就用下面的图文进行数学上的解释:

   下面小编给上这个题目的代码以及提交结果:

 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {//对于中间节点的问题我们优先使用快慢指针ListNode* p1 = head,*p2 = head;while(p2 != NULL && p2 -> next != NULL ){p1 = p1 -> next;p2 = p2 -> next -> next;}return p1;
}

     是不是觉得快慢指针很神奇呢?下面还有更神奇的等着大家,下面跟上小编的步伐,我们继续探索快慢指针世界!

2.2.环形链表

  老规矩,先给上链接:141. 环形链表 - 力扣(LeetCode) 

  这个题目还是有一点难度的, 不过没有那么的难,这个难度还是可以让人接受的,小编当时看到这个题目的时候,立马就想到了快慢指针,因为当时小编刚学不久,所以快慢指针这个方法想起来比较快,如果让一个月后的小编去看这道题,小编可能脑子直接宕机,下面废话不多说,小编开始比讲述我们如何运用快慢指针来判断这个链表是否是循环的:

  首先,我们照常设置两个指针和加一个循环,照常让慢指针往后走一步,快指针往后走两步,然后循环条件还是那个,不过此时我们需要在循环里加上一个if语句,这个语句来判断快慢指针是否相等,如果相等的时候直接返回true,如果循环结束了,直接返回false,读者朋友肯定很好奇小编为什么这么做呢?不要着急,下面听小编娓娓道来:首先,如果这个链表是循环链表的话,快慢指针肯定会相遇的,至于为什么相遇,小编在后面会通过数学推理来给各位解答的!其次,为什么循环结束以后就直接返回flase呢?这个很简单,如果这个链表不是循环的,那么快指针会直接出链表,不会在返回去,所以如果循环结束了,也就代表着这个链表是不循环的,下面小编先给上图文让各位读者朋友有更好的理解:

  先把慢指针和快指针设置好:

  让short1向后走一步,long1向后走两步:

   重复上述步骤:

  现在已经开始初见端倪了,下面我们继续重复上面的步骤:

  此时我们已经惊喜的发现,short1和long1两个指针终于相遇了,此时正是说明了此链表是循环链表,那么很多读者到这里会很好奇为啥这俩就能相遇呢?莫急,小编现在就通过图文来对大家进行图文解释:

   下面小编给出代码和提交图:

 typedef struct  ListNode  ListNode;
bool hasCycle(struct ListNode *head) {ListNode * n1 = head,*n2 = head;while(n2 && n2 -> next){n1 = n1 -> next;   //慢指针n2 = n2 -> next -> next;   //快指针if(n1 == n2)return true;}return false;
}

   读者朋友是否感觉到了快慢指针的妙处,小小的两个指针却可以解决出很大的问题,我相信现在很多读者朋友已经迫不及待的期待下一个题目的讲解了,不要着急,紧跟小编的步伐,咱们进入下一个习题的讲解!

2.3.链表的回文结构

  老规矩,先展示一下这个题目:链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

   这个题目我觉着很多读者朋友可能做过类似回文数的题目,我们把1221这种,从中间开始分,往左右读取数据一样的数称之为回文数,链表的回文结构也是这样的,就比如如图上面的测试样例:1 -> 2 -> 2 ->1,从中间向左右读取,我们便可以知道这是一样的,所以这就是有着回文结构的链表,对于这个题,小编当初是想着把链表的数据都放入到数组里面,我们可以通过除法的方式来找到中间的数,然后从这里开始向左向右读取的,毕竟,数组这个连续的结构还是蛮好用的,不过此时我相信很多读者朋友已经读取到关键信息了,找中间结点,这不就是我们的第一题?所以此时我们还是用到了我们的老伙计:快慢指针,我们可以通过快慢指针来找中间结点,找完中间节点以后,我们需要分别两个方向来进行结点数据的判定,我们可以从两头到中间来进行数据的判定,这时我们就用到了上个博客我们写过的反转链表的方法了,我们可以把中间结点之后的结点方向反转过来,此时就用到了小编之前写过的反转链表的方法,通过三个指针来实现链表方向的调转,对于具体内容,可以参考小编的上篇文章:单链表相关习题(超详细!)(1)-CSDN博客,小编这里就不在写如何进行反转了,下面直接展示代码:

class PalindromeList {ListNode* panduankuaiman(ListNode * A){ListNode  *shr = A,*quick = A;while(quick != NULL && quick -> next != NULL){shr = shr -> next;quick = quick -> next -> next;}return shr;}
public:bool chkPalindrome(ListNode* A) {// write code hereListNode * newecode = panduankuaiman(A);ListNode * a = NULL,*b = newecode,*c = newecode -> next;while(b){b -> next = a;a = b;   //好好理解这里,犯了一点小迷糊了b = c;if(c != NULL)c = c -> next;}ListNode * pour = A;while(pour < a){if(pour -> val != a -> val)return false;pour = pour -> next;a = a -> next;}return true;}
};

  这个题目是把两个题目进行了结合,这里可以看出知识之间是连续的,所以各位读者朋友一定要温故而知新 ,这一点对于我们之后计算机的学习有很大的帮助?下面进入本文最后一个题目的讲解!

2.4.环形链表Ⅱ

  老规矩,先给上题目的链接:142. 环形链表 II - 力扣(LeetCode)

  首先我们先来看一下这个题目的难度等级,中等,我们前面的题目无论多么复杂难度都是简单,到这里直接成为中等题了,足以说明这个题目的难度,难道这个题目非常难吗,这里小编可以明确的各位,其实这个题目就是纸老虎,我们知道这个题目的底层逻辑之后,这个题目甚至比前面的题都要简单!这个题目是想让我们去求循环链表开始循环的第一个结点,其实当初的小编做这个题的时候,一点思路也没有,直到听完了题目讲解小编才知道这个题是怎样的,下面小编给出这个题目的求解方式:

  这个题目与循环链表的不同之处在于,这个题目除了快慢指针以外,我们还需要多设置一个指针,这个指针首先要指向头结点,此时我们先不管指针,我们需要先利用快慢指针来判断这个链表是否是带环的,如果不带环,直接返回NULL,如果带环,我们需要记住快慢指针第一次相遇的位置,此时我们直接结束循环,然后此时我们设置的第三个指针开始与慢指针保持同样的速度,然后我们通过循环,循环的条件还不用管,此时我们首先开始判断慢指针和这个指针是否相等,不相等的话直接让他俩同时走,当他们相等的时候,这个时候,第三个指针指向的结点就是入环点!是不是感觉很神奇,下面小编在通过图文让各位读者朋友感受这个过程:

  我们直接快进到快慢指针相遇的时候:

  此时二者还不相等,让pour和short1同时往后走:

   此时pour和short1已经相等了,我们此时可以发现pour所指向的结点就是入环的结点,是不是感觉很神奇?可能很多读者朋友到这里会感到很懵,下面小编同样用数学的方法来给各位读者做出解释:

   这个题目如果知道了方法,其实很好做的,所以小编才说它是纸老虎,但是如果这个方法不知道的话,那么这个题目就是一个很难的题目了,希望各位读者朋友明白这个题目的解法!

总结:

  可算写完这篇文章了,其实小编在很久之前便起草了这一篇文章,不过小编还是偷懒了,今天才开始对这篇文章进行了补充,不得不说时间过得是真快,这么快就来到了七月末,离小编的十篇文章还差一篇就写完了,小编决定明天继续更文章,为了巩固我学过的知识,如果文章有错误可以在评论区指出,小编会接受大家的意见,那么我们下一篇文章见喽!

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

安全基础学习-CRC理解与计算

由于一些任务要求需要了解CRC校验&#xff0c;于是来学习一下。 新人学习&#xff0c;大佬绕路。 前言 CRC即循环冗余校验码&#xff1a;是数据通信领域中最常用的一种查错校验码&#xff0c;其特征是信息字段和校验字段的长度可以任意选定。循环冗余检查&#xff08;CRC&…

Seata 入门与实战

一、什么是 Seata Seata 是一款开源的分布式事务解决方式&#xff0c;致力于提供高性能和简单易用的分布式事务服务。Seata 为用户提供了 AT、TCC、SAGA 和 XA 事务模式&#xff0c;为用户打造一站式的分布式事务解决方案。 二、Seata 组成 事务协调者&#xff08;Transacti…

Potree点云可视化库在Vue项目中的应用

本文由ScriptEcho平台提供技术支持 项目地址&#xff1a;传送门 Potree点云可视化库在Vue项目中的应用 应用场景介绍 Potree是一个用于大规模点云渲染和交互的开源JavaScript库。它提供了高效的点云可视化和处理功能&#xff0c;广泛应用于地理信息系统&#xff08;GIS&…

整理几个常用的Linux命令(Centos发行版)

如果工作中需要经常整理一些文档&#xff0c;需要汇总一下&#xff0c;现有的服务器资源信息&#xff0c;那么这篇文章适合你&#xff1b; 如果你是一名开发者&#xff0c;需要经常登录服务器&#xff0c;排查应用的出现的一些问题&#xff0c;那么这篇文章适合你&#xff1b;…

《最新出炉》系列初窥篇-Python+Playwright自动化测试-61 - 隐藏元素定位与操作

软件测试微信群&#xff1a;https://bbs.csdn.net/topics/618423372 有兴趣的可以扫码加入 1.简介 对于前端隐藏元素&#xff0c;一直是自动化定位元素的隐形杀手&#xff0c;让人防不胜防。脚本跑到隐藏元素时位置时报各种各样的错误&#xff0c;可是这种隐藏的下拉菜单又没…

【创新实践新纪元】SmartEDA如何引领学校电子设计实践基地的飞跃式发展

在这个日新月异的科技时代&#xff0c;电子设计已成为推动社会进步与创新的重要力量。而教育&#xff0c;作为培养未来科技人才的摇篮&#xff0c;如何更有效地提升学生的实践能力与创新思维&#xff0c;成为了摆在每所学校面前的重大课题。今天&#xff0c;就让我们一同探索Sm…

列表内容过多卡顿?有索引栏如何实现滚动加载?

&#x1f453;写在前面 很多小伙伴可能在开发业务中会遇到这种问题&#xff0c;数据列表过多&#xff0c;造成dom一次性渲染卡顿&#xff0c;本文主要介绍滚动加载&#xff0c;实现在有索引栏的列表中使用滚动加载的方法。 本文技术栈使用的是vue2vant2&#xff0c;其他框架组…

阿里云服务器 Ubuntu18.04 安装 mysql8.0并允许外部连接

参考教程&#xff1a; 官网教程 参考教程一 首先彻底删除mysql5.7 dpkg --list|grep mysql #查看 sudo apt-get remove mysql-common #卸载 sudo apt-get autoremove --purge mysql-server-5.7 #版本自己修改 dpkg -l|grep ^rc|awk {print$2}|sudo xargs dpkg -P #清除残留数…

vite打包文件配置到IIS出现页面、图片加载不出来的问题

问题描述&#xff1a; 用vitevue3开发的项目&#xff0c;打包后放在服务器上&#xff0c;然后配置了IIS&#xff0c;用链接访问后出现白页面。 解决方案&#xff1a; 修改vite.config.js文件中的base路径&#xff1a;/改为./ 解决方案&#xff1a; 1.查看页面报错原因&…

归并排序 python C C++ 代码及解析

一&#xff0c;概念及其介绍 归并排序&#xff08;Merge sort&#xff09;是建立在归并操作上的一种有效、稳定的排序算法&#xff0c;该算法是采用分治法(Divide and Conquer&#xff09;的一个非常典型的应用。将已有序的子序列合并&#xff0c;得到完全有序的序列&#xff…

二叉树——链式结构的实现

首先是分为三个文件进行实现&#xff1a;tree.h、tree.c、test.c tree.h 用链表来表示⼀棵⼆叉树&#xff0c;即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成&#xff0c;数据域和左右指针域&#xff0c;左右指针分别用来给出该结点左孩⼦和右孩⼦所在…

一键解析:由于找不到xinput1_3.dll,无法继续执行代码的问题,有效修复xinput1_3.dll文件

xinput1_3.dll是一个重要的动态链接库文件&#xff0c;它是DirectX软件包的一部分&#xff0c;主要负责处理游戏和多媒体应用程序中的输入功能。当用户尝试启动某些游戏或应用程序时&#xff0c;可能会遇到一个错误提示&#xff0c;指出“由于找不到xinput1_3.dll&#xff0c;无…

TypeScript 的主要特点和重要作用

还是大剑师兰特&#xff1a;曾是美国某知名大学计算机专业研究生&#xff0c;现为航空航海领域高级前端工程师&#xff1b;CSDN知名博主&#xff0c;GIS领域优质创作者&#xff0c;深耕openlayers、leaflet、mapbox、cesium&#xff0c;canvas&#xff0c;webgl&#xff0c;ech…

《昇思25天学习打卡营第三十三天|7月26号》

昇思25天学习打卡营 在昇思25天学习打卡营的第33天7月26号&#xff0c;我深入学习了Python编程。通过课程的系统学习和实践编程项目&#xff0c;我逐渐掌握了Python语言的基本语法和核心概念。 特别是在函数定义和数据结构的应用上&#xff0c;我学习到了一些新的东西。以为平…

苹果手机怎么录屏?一键操作,轻松掌握录屏技巧

最近新换了一台苹果手机&#xff0c;但苹果手机和安卓手机有挺多不相同的地方&#xff0c;就比如苹果手机怎么录屏我一直都没找到&#xff0c;有没有经常使用苹果手机的朋友可以帮帮我&#xff1f;先谢谢大家啦&#xff01;” 苹果手机作为全球领先的智能手机品牌&#xff0c;…

layui 乱入前端

功能包含 本实例代码为部分傻瓜框架&#xff0c;插入引用layui。因为样式必须保证跟系统一致&#xff0c;所以大部分功能都是自定义的。代码仅供需要用layui框架&#xff0c;但原项目又不是layui搭建的提供解题思路。代码较为通用 自定义分页功能自定义筛选列功能行内编辑下拉、…

面试经典算法150题系列-数组/字符串操作之多数元素

序言&#xff1a;今天是第五题啦&#xff0c;前面四题的解法还清楚吗&#xff1f;可以到面试算法题系列150题专栏 进行复习呀。 温故而知新&#xff0c;可以为师矣&#xff01;加油&#xff0c;未来的技术大牛们。 多数元素 给定一个大小为 n 的数组 nums &#xff0c;返回其…

“华数杯”全国大学生数学建模竞赛含金量如何?

“华数杯”全国大学生数学建模竞赛是由华中师范大学主办的一项全国性的大学生数学建模竞赛。该竞赛旨在提高大学生的数学建模能力和实践能力,增强大学生的创新意识和团队协作精神。 搜集一些评价,有人说该竞赛的含金量较高,但是也有一些人认为其认可度不高,报名费用较贵。…

javascript 构造函数

1.定义一个构造函数 命名是大驼峰 不需要显式得返回 this对象 构造函数已返回 2.使用这个构造函数构建对象

锅总浅析链路追踪技术

链路追踪是什么&#xff1f;常用的链路追踪工具有哪些&#xff1f;它们的异同、架构、工作流程及关键指标有哪些&#xff1f;希望读完本文能帮您解答这些疑惑&#xff01; 一、链路追踪简介 链路追踪技术&#xff08;Distributed Tracing&#xff09;是一种用于监控和分析分布…