请问在查找单链表环时那个快的指针的步长为什么是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，当快的接近慢的时候，有可能跳过慢的节点。其实画个图啥都明白了
相关推荐
查看30道真题和解析 点赞 评论 收藏
分享
投递携程等公司10个岗位 >