Leetcode 141.环形链表 142环形链表II
创始人
2024-06-01 16:51:34
0

141环形链表

文章目录

  • 快慢指针

快慢指针

代码思路:

slow 和fast 指向 head slow走一步,fast走两步

没有环:

fast每次走2步 ,如果 fast 最终遇到NULL(链表中的元素是 偶数)或者fast->next(链表中的元素是 奇数)遇到NULL,说明链表中没有环

在这里插入图片描述

有环:

如果 fast 和 slow指针在途中相遇 ,说明这个链表有环

因为fast 比slow 走的快 , 如果 fast 最终和 slow 相遇,那肯定是 fast 超过了 slow 一圈,说明链表中含有环。

bool hasCycle(struct ListNode *head){struct ListNode * slow =head , * fast = head ;//假设带环while ( fast!= NULL && fast->next != NULL){ fast =fast->next->next ;slow = slow->next ;if( slow  == fast )  //因为fast每次走2步 ,slow每次走一步 如果有环 那一定是fast追上slow 也就是相遇{return true ;}}//fast 为NULL 或者 fast->next 为NULL    如果 fast 最终遇到空指针,说明链表中没有环 return false ; 
}

我们证明一下这个逻辑问题:

为什么 slow 走一步 fast 走两步 ,fast 和slow 会相遇 ,有没有可能会错过

假设slow 刚开始进环的时候 slow 和fast 的距离是N ,slow开始进环的时候 fast开始追及slow ,因为fast 每次走两步 ,而slow 每次走一步 ,也就是说在追及的过程中 fast 与slow每次缩短一步的距离
不管N 是否为奇数还是偶数 , N每次减一 ,迟早为0 ,也就意味着fast 追上了 slow

在这里插入图片描述

那我们再推广一下

如果slow 走一步 ,fast 走 X 步( X >=3) ,fast 和slow 会相遇 ? 或者有可能错过?
假设slow刚开始进环 ,fast 和slow 的距离是N
slow进环以后 fast 开始追及slow ,slow每次走一步 ,fast 就走三步 ,距离缩小 2 步
如果N 是偶数 N -2 , N-4 , N - 6 , 4 , 2 …N可以减到零
如果N 是奇数 N -2 , N-4 , … 3 ,1, -1
我们假设环的周长是C ,N 是 -1 , 也就是说 fast 和slow 的距离变成了 C-1 ,又开始了新的一轮追及

在这里插入图片描述


142.环形链表II

结论 : 一个指针(fast)从相遇点开始走 ,一个指针(slow)从起始点开始走 ,会在入口点相遇

结论千万不要理解为slow 去追fast 了 ,其实是fast追slow ,只不过fast走的快 ,可能在环里转了n 圈
一旦slow走到入口点 ,fast 就会和slow 相遇

下面我们来证明一下上述结论:
假设起始点到入口点处的距离是L , 入口点处到相遇点的距离为X
环的长度为C
在这里插入图片描述

那么可以推出slow 走的距离为L + X ,
fast 走的距离是 L+ n* C + X ,
n* C 表示 slow 进环前 ,fast 在环里转了n*C 圈

根据fast 走的距离 是slow 的两倍
2(L+X ) = L + n *C + X
推出 L= n * C -X

将这个推导式变形 得到 L = ( n -1) * C + C -X
即证明结论成立

struct ListNode *detectCycle(struct ListNode *head){struct ListNode * fast = head , * slow = head ;// 假设带环while ( fast != NULL && fast->next!=NULL){slow =slow->next ;fast =fast->next->next ;if( slow == fast )  {struct ListNode * meet = fast  ;  //相遇点struct ListNode * start = head ;//起始点while( meet!= start ) // 一个指针(fast)从相遇点开始走 ,一个指针(slow)从起始点开始走 ,会在入口点相遇{meet= meet->next ;start=start->next ;}return meet ;}}return NULL ; //不带环}

如果你觉得这篇文章对你有帮助,不妨动动手指给点赞收藏加转发,给鄃鳕一个大大的关注
你们的每一次支持都将转化为我前进的动力!!!

相关内容

热门资讯

鸿蒙怎样还原安卓系统,系统切换... 你有没有想过,鸿蒙系统竟然能还原安卓系统?这听起来是不是有点像魔法一样神奇?没错,今天就要带你一探究...
电脑安卓转苹果系统,系统迁移攻... 你有没有想过,有一天你的安卓手机突然变成了苹果的忠实粉丝,想要跳槽到iOS的阵营呢?这可不是什么天方...
安卓xp系统下载地址,轻松获取... 你有没有想过,手机系统也能穿越时空?没错,今天我要给你揭秘的就是这样一个神奇的存在——安卓XP系统。...
安卓系统怎么清理相册,安卓系统... 手机里的相册是不是越来越臃肿了?每次打开都感觉像是在翻山越岭,找一张照片都要费老鼻子劲。别急,今天就...
安卓系统安装ios转移,轻松实... 你有没有想过,手机系统之间的转换竟然也能如此神奇?没错,今天就要来聊聊安卓系统安装iOS转移这个话题...
安卓系统与ios系统的优势,系... 你有没有想过,为什么你的手机里装的是安卓系统而不是苹果的iOS系统呢?或者反过来,为什么你的朋友用的...
安卓系统游戏如何升级,轻松实现... 亲爱的安卓玩家们,你是否也和我一样,对安卓系统游戏升级这件事充满了好奇和期待呢?每次游戏更新,都仿佛...
安卓系统蛋仔派对,安卓系统下的... 你有没有发现,最近你的手机里多了一个超级好玩的游戏?没错,就是安卓系统上的“蛋仔派对”!这款游戏可是...
坚果3安卓原生系统,深度体验原... 你有没有听说过坚果3这款手机?它可是最近在数码圈里火得一塌糊涂呢!今天,我就要来给你详细介绍一下这款...
安卓子系统点不开,排查与解决指... 最近是不是你也遇到了安卓子系统点不开的烦恼?这可真是让人头疼啊!别急,今天就来给你详细解析一下这个问...
安卓系统经常误删文件,如何有效... 你有没有遇到过这种情况?手机里的文件突然不见了,找来找去,怎么也找不到。别急,这可能是安卓系统的小调...
安卓51系统如何破解,轻松解锁... 安卓51系统如何破解——探索未知的技术边界在数字化时代,手机已经成为我们生活中不可或缺的一部分。而安...
安卓系统怎么换回主题,安卓系统... 亲爱的手机控们,你是不是也和我一样,对安卓系统的主题换换换乐此不疲呢?不过,有时候换着换着,突然发现...
黑莓安卓系统 太垃圾,令人失望... 你有没有用过黑莓的安卓系统?别告诉我你没有,因为现在这个系统真的是太垃圾了!是的,你没听错,就是那个...
修改安卓系统权限代码,安卓系统... 你有没有想过,你的安卓手机里那些神秘的系统权限代码?它们就像隐藏在手机里的秘密通道,有时候让你觉得既...
虚拟大师安卓系统教程,教程详解... 你有没有想过,手机里的世界可以变得更加神奇?今天,就让我带你一起探索虚拟大师安卓系统的奥秘吧!想象你...
基于安卓系统个人博客,轻松构建... 你有没有想过,在这个信息爆炸的时代,拥有一片属于自己的网络小天地是多么酷的事情啊!想象每天都能在这里...
安卓怎么传到苹果系统,从安卓到... 你是不是也有过这样的烦恼:手机里存了好多好用的安卓应用,可是一换到苹果系统,就发现这些宝贝们都不见了...
安卓改系统字体app,安卓系统... 你有没有想过,手机上的字体也能变得个性十足?没错,就是那个安卓改系统字体app,它可是让手机界面焕然...
安卓系统重启密码错误,破解与预... 手机突然重启了,屏幕上竟然出现了密码输入的界面!这可怎么办?别急,让我来帮你一步步解决这个安卓系统重...