142. Linked List Cycle II

思路

首先要证明链表有环： 用快慢两个指针解决。快指针每次走两步，慢指针每次走一步。如果有环，则一定会最终在环内某点相遇。下面证明这一点：

假设慢指针进入环时，快指针在环内某点，且其前进方向与慢指针相差s步。那么根据运动规律，每次满指针走一步，快指针走两步，快、慢指针的距离会减少一步。所以，经过s轮，快指针一定会追上慢指针。

IMG_20180920_160025.jpg

然后要找到环的入口：

如上图，假设两个指针在某点相遇，则慢指针走了a + b步，快指针走了a + (b + c) + b + nr步（其中n>=0，环的长度是r，则b + c = r是一环的长度。快慢指针相遇时，快指针至少领先慢指针一环，所以有(b + c)） 由于快指针走了慢指针的两倍路程，有： 2(a + b) = a + (b + c) + b + nr 得： a = c + nr，n>=0 所以a的长度比c长n圈。

我们让一个指针从链表头开始，另一个指针从相遇点开始，每次各走一步，由于a = c + nr，当从链表头出发的指针经过a步到环入口时，从相遇点出发的指针先经过c步返回入口处，又绕着环走了n圈，依旧回到入口。所以两个指针一定会在环入口处相遇。

如此，就找到环的入口了。