请问在查找单链表环时那个快的指针的步长为什么是2?3倍4倍？
请问在查找单链表环时那个快的指针的步长为什么是2?3倍4倍？
请教。。。
第一：为什么使用快慢指针就可以判断有环？
第二：为什么快指针是步长为2？ 为3 为4 不可以么？
帮忙证明一下 thank
2016-08-06 21:25 已编辑 杭州电子科技大学 C++
关注
全部评论
牛客906907号
这是为了保证慢指针能尽快和快指针相遇，假如从起点到环入口长为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
牛客3511511号
有环表示经过一段时间会回到起点，步长为2，若有环一定会在同一个节点相遇，若为大于2，当快的接近慢的时候，有可能跳过慢的节点。其实画个图啥都明白了
相关推荐
不愿透露姓名的神秘牛友
07-03 17:26
码农索隆：我就问一下，你性格真内向吗
点赞 评论 收藏
分享
07-01 17:42
哈尔滨工程大学 机械工程师 点赞 评论 收藏
分享
06-12 17:46
门头沟学院 Java 
运营你豪哥：来说重点：
1.项目前置，时间倒序。
2.项目描述强化结果与量化效果（STAR原则里的R）。
3.个人技能精炼，明确掌握程度，突出核心。
4.增加强有力开头的个人总结部分。
5.优化教育背景（成绩排名）、合并奖项与活动。 点赞 评论 收藏
分享
07-04 16:00
门头沟学院 Java 
投递字节跳动等公司9个岗位 点赞 评论 收藏
分享