Floyd 判圈算法

在链表的问题中，使用快慢指针的技巧可以解决判断链表中是否存在环的问题，但如果我们需要知道环的入口在哪儿的话该怎们办呢？我们可以更进一步的研究这个问题。

flowchart LR

%% nodes

a((A)) --> b((B)) --> c((C)) --> d((D)) --> e((E)) --> f((F))
f --> c

以上图的链表所示，我们假设从头到第一个环的距离为 $p$ ，环的长度为 $c$ , 快慢指针相遇时的点距离环入口的距离为 $x$ ，$n$ 和 $n^{\prime }$ 表示快慢指针在环中走过的圈数，因为快指针走过的距离始终是慢指针的两倍，我们可以得出以下等式：

$$2(p+n^{\prime }c+c-x)=p+nc+c-x$$

化简可得：

$$p=(n-2n^{\prime }-1)c+x$$

意味着，从链表头到入环点的距离 $p$ ，恰好等于相遇点距离入环口的距离 $x$ 加上若干圈环的距离，如果我们这时重新设置一个指针指向头，一个指针指向相遇的节点，再以每次一格的速度移动，那两个指针必定在环的入口处相遇，此时我们便找到了环的入口。