佛系编码 level
获赞
43
粉丝
18
关注
0
看过 TA
25
杭州电子科技大学
2017
C++
IP属地:河北
路漫漫其修远兮
私信
关注
2016-09-17 18:25
已编辑
杭州电子科技大学 C++
0 点赞 评论 收藏
分享
2016-08-06 21:25
已编辑
杭州电子科技大学 C++
请问在查找单链表环时那个快的指针的步长为什么是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
0 点赞 评论 收藏
分享
关注他的用户也关注了:
牛客网
牛客企业服务