链表带环问题简单讲解

  #带环链表

解题思路

对于这道题我们可以定义两个指针，一个快指针，一个慢指针。

快指针一次走两步，慢指针一次走一步。这样快指针就会比慢指针先进入环内。

慢指针进入环后，这个问题就会演变成一个追击问题，即：快指针能否追上慢指针并与之重合。

假设，慢指针进入环后与快指针的距离为N。因为快指针速度为2，慢指针速度为1，所以两个指针每走一次都会使N-1，当N=0时，快指针与慢指针相遇。

因为两指针每次移动缩减的距离为1，N势必会等于0，而且不存在快指针越过慢指针的情况。所以快指针一定会与慢指针相遇。

数学扩展

如果快指针每次走三步、四步、五步，那存不存在快指针每次都会越过慢指针，从而使两者永远无法相遇的情况？

慢指针进入到环以后，快慢指针距离为N，两指针的速度差为sub，环的周长为C。

因为两指针的运动是相对的，我们可以把慢指针视为不动，快指针以sub的速度在动

当快指针未超过慢指针就与其相遇时，快指针走的距离为N，两指针的距离为N。

当快指针超过慢指针走了一个完整圆环再与慢指针相遇时，快指针走的距离为N+C，两指针的距离相当于N+C。

以此类推：

当快指针超过慢指针走了K个完整圆环再与慢指针相遇时，快指针走的距离为N+K*C，两指针的距离相当于N+K*C。

当两指针间的距离能被sub整除时，说明两指针能相遇。

于是得出两指针相遇的公式：(N+K*C)%sub==0

#求环接入点

解题思路

我们创建两个指针，快指针速度为2，慢指针速度为1。

慢指针进入环时走的距离为X，快指针走的距离为2X。
 

在环中，当快指针与慢指针相遇时，快指针走的距离为2t，慢指针走的距离为t。

我们可以发现N+t=2t     由此我们能得出：t=N

我们发现快指针走的总距离为2X+2N，慢指针走的距离为X+N。

也就是：快指针走的总距离=2*慢指针走的总距离

那快指针再环里走了几圈呢？

不知道，我们设：快指针在环里走了K圈，环的周长为C。

快指针走的总距离又可以表达为：X+K*C+N

所以可得：快指针走的总距离=2*慢指针走的总距离

              ->   X+K*C+N=2*（X+N）

              ->  K*C-N=X

              ->  (K-1)*C+(C-N)=X         快指针在环中必转一圈（否则无法相遇），所以K>0。

C-N正好是指针1到环接入点的距离。

也就是说：两指针相遇后，让一个指针留在原地，另一个指针放到起始点，两个指针同时向后遍历链表（就是两指针速度为1），就可以得到环的接入点了。