请问在查找单链表环时那个快的指针的步长为什么是2?3倍4倍？

请问在查找单链表环时那个快的指针的步长为什么是2?3倍4倍？
请教。。。
第一：为什么使用快慢指针就可以判断有环？
第二：为什么快指针是步长为2？  为3  为4  不可以么？
帮忙证明一下     thank
全部评论
这是为了保证慢指针能尽快和快指针相遇，假如从起点到环入口长为x，相遇是慢指针离环入口为 t 环长度为 s ，假设快指针为慢指针 k倍 ，慢指针在环内走了n圈，快指针走了q圈相遇，则k*（x+ns+t）=x+t+qs 则（k-1）（x+t） =(q-n)s 为了然慢指针尽量和快指针相遇，因此n=0. ，此时q=（k-1）（x+t）/s，由于s一定，x+t一定，因此为了让q最小k=2
4 回复 分享
发布于 2016-08-08 11:23
有环表示经过一段时间会回到起点，步长为2，若有环一定会在同一个节点相遇，若为大于2，当快的接近慢的时候，有可能跳过慢的节点。其实画个图啥都明白了
点赞 回复 分享
发布于 2016-08-06 21:22

相关推荐

03-28 21:30
歌尔股份_信息技术支持(准入职员工)
歌尔股份内推
硕士40W起/博士50W起+安居补贴+其他多种高额福利，看到公告里的这个信息，立马燃起了单独更他的欲望～ 其实很多人也许对这个企业名字比较陌生，但是他代工的零件/产品还是咱们超多人在用的～ 它曾经是苹果 AirPods 的生产商,现在也是苹果 Vision Pro 供应链的一部分，虽然果链断了，1800yi的估值严重缩水，但随着“华链”在中国的崛起，它也开始逐步向好发展～ - Goertek 歌尔集团 成立于2001年6月，2008年5月在深交所上市，是全球布局的科技创新型企业、虚拟现实与智neng硬件领域全球领先企业 ✅2023年公司位列中国电子元器件骨干企业100榜单第4位 ✅中国电子信息...
歌尔股份晋升空间 7人发布
点赞 评论 收藏
分享
03-28 12:03
已编辑
北京外国语大学 平台产品
不要害怕做选择
20多岁的时候，我总觉得人到了一定年纪之后，比如30岁，那一定是从容、自信、游刃有余，不会再为一些世俗的欲望而迷茫，也不会再为还没有发生的事情提前焦虑。但是我今年29了，距离30岁只有一年，我依然没有成为自己想象中的“意志像钢铁，姿态像流水的人”，我大多时候都很焦虑，依旧很害怕做选择，也依旧迷茫。迷茫和焦虑意味着我总是在各种可能的选项之间，做趋利避害分析，而任何潜在的我没有提前预判到的风险一旦出现，都会击溃我的自信。一旦自信被击溃，我便开始附和、开始被动、开始打退堂鼓，显得漏洞百出。身边的人对我的状态非常敏感，也幸好我有一个非常好的朋友，他总是提醒我：做什么选择都没关系，只要你是自信的。这句话...
萌新材料王：很多时候我们都忘了，自己来到这个世界上是看太阳怎么升起怎么落下
牛友故事会
点赞 评论 收藏
分享
03-20 18:39
已编辑
电子科技大学 C++
点赞 评论 收藏
分享
03-29 15:01
已编辑
哈尔滨工业大学（威海） 算法工程师
面经·拼多多服务端研发一面
笔试40分钟AK满分。面试官提前了一分钟到场让我很意外，面了三场了（蚂蚁一二面，字节一面），这是第四场，提前到的是第一个。自我介绍，非科班，去年开始自学计算机……然后他让我介绍项目。然后开始问项目内容。然后问项目几个人。然后问为什么小项目要用高并发，我说不用点技术显得一点技术都没，都笑了。然后问我个人技能，他是第一个问提示词工程的。然后网安这边也稍微问了问。终于进入八股环节，行级锁，我看黑马的课锁还没看完，如实说了，问index，我稍微讲了讲，问事务，稍微讲了讲，问行级锁和事务有啥关系，不晓得呢。问死锁的一个情景，答错了。…………可恶，盯着锁问，课还没看完呢。然后我忘了。最后进入手撕环节（他说...
Brianmay：大佬算法有点强
查看16道真题和解析
点赞 评论 收藏
分享
评论
点赞
4
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 笔试 #
2304453次浏览 26998人参与
# 实习期间如何提升留用概率？ #
7393次浏览 139人参与
# 招行数字金融训练营 #
192751次浏览 568人参与
# 牛友故事会 #
466155次浏览 11013人参与
# 应届生简历当中，HR最关注哪些？ #
11559次浏览 145人参与
# 什么专业适合考公 #
24495次浏览 181人参与
# 腾讯云智研发2025实习生招聘 #
121479次浏览 1448人参与
# 大厂还是考编 #
80188次浏览 1300人参与
# 求职你最看重什么？ #
57480次浏览 332人参与
# 机械/制造每日一题 #
53201次浏览 944人参与
# 毕业季，你想好怎么跟生活对线了吗？ #
183647次浏览 3420人参与
# 牛友春招想让哪家公司来捞你？ #
26734次浏览 166人参与
# 虾皮求职进展汇总 #
208927次浏览 1452人参与
# 机械人，说说你的烦心事 #
57105次浏览 784人参与
# 京东工作体验 #
11401次浏览 82人参与
# 实习必须要去大厂吗？ #
81666次浏览 1226人参与
# 我想象的实习vs现实的实习 #
267406次浏览 2160人参与
# 得物app工作体验 #
14340次浏览 52人参与
# 你的秋招简历被谁挂了？ #
244817次浏览 2652人参与
# 文科生还参加今年的春招吗 #
8011次浏览 87人参与
# 职场破防瞬间 #
73545次浏览 901人参与
# 牛友的五一计划 #
60379次浏览 665人参与
牛客网
牛客企业服务