快慢指针解决链表中的环问题

问题描述

给定一个链表，判断链表中是否有环。环的起点在哪里，环的大小是多少。

一、边界条件

若链表没有环，那当快指针指到nullptr时，表示该链表没有环。

二、推导快慢指针相遇的地方

快指针速度：2
慢指针速度：1

当慢指针走到P2点时，不妨设快指针走到P1点。并设P1与P2间距离为D，
此时可列等式：
慢指针走的距离 * 2 =快指针走的距离
2 ∗ K = K + D + n ∗ R . 2*K =K + D+n * R. 2∗K=K+D+n∗R.
其中n为快指针已经走过环的圈数。

由上式可以推出
K = D + n ∗ R . K = D+n * R. K=D+n∗R.
由图中我们可以得知，P1与P2点相距D距离，则快指针追赶上慢指针则需要比慢指针多走（R-D）距离。
由此我们可以列式得出：
相距距离 / 速度差值 = 相距仍需要走的步数
R − D 2 − 1 = R − D , . \frac{R-D }{2-1}=R-D,. 2−1R−D​=R−D,.
快指针的速度为2，那么我们就可以得到相遇的点为2（R-D）+D=2R-D，
也就是P3点，该点距离P2点的距离为D，与P1对称。

三、推导环的入口点

推导相遇过程中，我们得到了一个等式， K = D + n ∗ R . K = D+n * R. K=D+n∗R.
那么我们就可以根据这个等式，重新设置两个指针，速度相同，起点不同， 一个起点设置在链表的头结点，而另一个则设置在相遇结点，根据上述等式，我们可以得知，两结点相遇的地方就是环的入口点。

四、环的大小

得到环的入口点，只需要遍历一遍环，即可得到环的大小。