单链表找环（floyd算法）

首先是示意图，链表中有环就是这种情况

image

问题是，在这样一个单链表中，若有环，寻找出环的入口

floyd算法是怎么做的呢？

1. 快慢指针，同时从起点开始走。

image

2. 设环路长度为l, 则当

<svg xmlns:xlink="http://www.w3.org/1999/xlink" width="19.297ex" height="2.577ex" viewBox="0 -806.1 8308.4 1109.7" role="img" focusable="false" style="vertical-align: -0.705ex;" class="in-text-selection"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><g transform="translate(5507,0)"><text font-family="STIXGeneral,'Arial Unicode MS',serif" stroke="none" transform="scale(50.259) matrix(1 0 0 -1 0 0)">是</text></g><g transform="translate(6311,0)"><text font-family="STIXGeneral,'Arial Unicode MS',serif" stroke="none" transform="scale(50.259) matrix(1 0 0 -1 0 0)">整</text></g><g transform="translate(7115,0)"><text font-family="STIXGeneral,'Arial Unicode MS',serif" stroke="none" transform="scale(50.259) matrix(1 0 0 -1 0 0)">数</text></g></g></svg>

时，快人和慢人相遇。

3. 这时我们并不知道相遇点在哪里，只知道它一定在环上。不过观察相遇条件那个式子，可得

而， 又等于慢人走过的总路程，慢人走过的总路程又可以分解成环外的部分和环上的部分。

4. 这样的总路程是环长的倍数，那是不是

慢人当前位置往前走“环外部分”步，换言之，把环外部分移动到环内

这样，就得到了一段从环入口开始，且长度为环长倍数的路程，这样的路程，终点仍然在环的入口。

5. 那么，怎么样才能做到呢？

很简单，引入第三个人，让他从起点开始走，当他走了“环外部分”步后，一定会和慢人在环路入口相遇。

这样就找到了问题的答案。