标签归档:快慢指针

RSS feed of 快慢指针

最后更新于 .

这是之前朋友出的一道题目,感觉不错,就拿来分享一下。
问题如下:
一个单向链表,怎么判断他是否存在环?

图示:

show

对于最简单的做法就是:
用一个指针走一圈,如果重复遇到其他任何一个指针,则证明有环。
但是这样做的问题就是:

单指针需要留下脚印,会弄脏链表数据,而如果不能脏数据的话,就需要增加一个容器,并且增加查找的开销。

有没有更好的方法呢?有的,定义一对快慢指针分别为ptr_fast,ptr_slow,ptr_slow走一步,ptr_fast走两步,如果ptr_slow和ptr_fast最终能相遇,那么证明有环。

解释如下:
画图:

show2

设步长分别为x和y,链表回环结点数为n,非环回环为m
设经过t次跨步,则只要xt和yt对n同余并且xt和yt都大于m就可以相遇(假设x>y)

xt-yt=pn
yt>m

得到:
t=pn/(x-y) > m/y(只需pn可整除(x-y))

指针移动次数为(x+y)t=(x+y)/(x-y)*pn

而要想pn永远整除(x-y ...