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 ; //不带环}

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

相关内容

热门资讯

存储芯片巨头的好日子何时结束 ... 摩根士丹利最新报告指出,旧存储芯片行业的前景被低估。曾经因供需失衡而获得高额利润的旧存储芯片现在正处...
国足开场2分钟落后 邵佳一眉头... 点击加载图片直播吧11月17日讯 国足开场2分钟丢球,0-1落后巴林,镜头给到眉头紧锁的邵佳一。国字...
小米:相关内容纯属虚构,警惕虚... 小米旗下微博账号“小米辟谣”于11月17日发布声明,指出近期有不法分子冒充“小米汽车”发送诈骗短信,...
最差密码榜单公布 123456... 网络安全公司 NordPass 发布了《2026 年最常用密码 Top 200》报告,指出“1234...
2岁孩子生命最后11天依然努力... 25岁的妈妈将患有罕见病的儿子兜兜送进了长沙的“雏菊之家”安宁病房。她陪伴儿子度过了最后11天,并每...
13岁少年被控杀害5岁男童案 ... 一名13岁少年因妹妹被邻居5岁男童撒沙而心生怨恨,将男童带至桥上推下水致其溺亡。此案引起了媒体的广泛...
全球顶尖科学家加速回流中国 风... 全球顶尖科学家纷纷选择离开美国,转向中国任职。2026年初,莱斯大学90后斯隆奖得主汪淏田全职加盟同...
APEC工商领导人峰会今天聚焦... 11月17日,来自亚太经合组织21个经济体及英国、法国、德国、瑞士等13个域外经济体的2000多位政...
雷军APEC发言 具身智能潜力... 11月17日,小米CEO雷军在2026年APEC工商领导人峰会上表示,具身智能机器人的潜力超过汽车,...
俄罗斯记者惊呼在深圳谁还用现金... 11月17日,今日俄罗斯国际通讯社记者德米特里·加夫里洛夫在接受采访时分享了他的深圳体验。他提到,刚...
雷军:智能机器人产业潜力超汽车... 11月17日,在2026年亚太经合组织工商领导人峰会上,小米CEO雷军介绍了公司在AI、智能制造和机...
保研举报成风,这不只是“坏人变... 保研举报成风,这不只是“坏人变小了” 制度留操作空间。高校保研季举报成风:这不是学生坏,是制度留了太...
广东01年医护女孩为00年闺蜜... 据河南广播电视台小莉帮忙,广东一位01年的女孩,亲自为自己00年的闺蜜接生。她们的缘分有多深?女孩称...
广东网友为迎接APEC会议周有... 11月14日,2026年APEC领导人会议周新闻中心举办了广东省、深圳市专场中外媒体吹风会。这是20...
动车插座在头顶被吐槽像在打吊瓶... 近日,有网友在社交平台发帖分享自己的乘车经历:乘坐D2928次动车组时,发现车厢内的充电插座安装在顶...
万斯称与特朗普无分歧 一致反对... JD·万斯周一表示,他与总统唐纳德·特朗普在伊朗战争问题上完全一致。此前,他曾将共和党在中期选举中的...
痛风人群这4种饮品要少喝 咖啡... 很多尿酸高、痛风人群都知道啤酒、果汁会升高尿酸,那么有没有什么饮料对尿酸“很友好”,甚至还能降低痛风...
医生辟谣左侧睡根本不伤心:正常... 11月17日,经常朝左睡对心脏的影响引发关注。从解剖学角度看,心脏虽然位于胸腔偏左,但它并非孤零零地...
96岁奶奶扒着车窗含泪送孙女返... 近日,湖南,假期快要结束,孙女准备返程。96岁的奶奶扒着车窗,眼里满是不舍。一句有空常回家看看,戳中...
人民日报:从《持械入宋》火爆看... 有能够让行业内外普遍认可的作品出现,是一种新文艺类型成熟的重要标志。正是因为“家里家外”系列、《盛夏...