从第141题已知,用快慢指针的方法可以判断是否链表存在环。
假设两个指针相遇时,快指针走过了m步进入环的入口然后转了k1圈(每圈n步)又多p步;同理,慢指针走过了m步进入环的入口然后转了k2圈又多p步。由于两者是两倍关系,所以 m+k1*n+p = 2*(m+k2*n+p)。
化简之后得到 m = (k1-2k2)*n-p,变换一下 p+m = (k1-2k2)*n
因为慢指针目前已经比整数圈多走了p步,结合这个数学式子,这说明如果慢指针再走m步的话,又会凑成整数圈,即到了环的入口。怎么确定m呢?只要另开一个指针从head开始与慢指针一齐走,它们相遇的地方就是环的入口。
本题的算法还有一个非常巧妙的应用:287. Find the Duplicate Number