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

问题描述

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

一、边界条件

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

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

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

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

三、推导环的入口点

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

四、环的大小

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