letcode:287. 寻找重复数：弗洛伊德的乌龟和兔子_floyd 龟兔 重复数

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数

letecode

其他解法就不说了，没什么，重点说下快慢指针乌龟和兔子这个的思想和证明，我第一次看到这种方法的时候，完全不知道为什么可以这样能找出答案。经过百度和几个小时的思考才想明白。

针对这道题，由于值是1~ n 且有n+1个数，那一定有重复值，并且只有一个重复数字，可以将数组想象成链表，数组中的值就是该节点的下一节点的地址。如果没有重复的数，那就是个无环的链表，如果数组中有重复的数字，那么就意为着节点中，有两个节点是指向同一个节点的，这就成了环。我们只要找环的入口点就是重复的数字即可。

如果数组中的值和索引对应，那么该节点自己就形成了一个自环，但是索引为0的节点肯定是不会在环内的，因为值是1~ n，没有节点指向0.
如下手画图 基本展示了所有可能出现的链式结构：

可以看到，0节点一定在循环外，而且一定有一个环链（因为只有一个重复数字）。
那现在的问就是如何找到这个环链的入口，上面这个例子就是4节点。返回4.

弗洛伊德的乌龟和兔子

我参考了这篇的解答，然后结合自己的想法稍微证了下.
设定两个对象“乌龟”和“兔子”，它们从链表的开始以不同的速度沿着链表遍历。乌龟每一步移动一个单元格，兔子每一步移动两个单元格。

如果兔子走到一个空的链接上，意味着这个链表有一个终点，也就是说没有循环。

如果这个链表包含一个循环，兔子最终一定会进入这个循环，并且开始沿着循环不停的绕圈。

与此同时，乌龟缓慢的沿着链表爬行，最终它也会进入这个循环。此时，兔子和乌龟都处于这个循环之中。
我们设需要T步进入循环节点。T=5.环内长为L=6.如下图：

令H为T步后兔子在循环中的位置距离循环开始点的距离。
由于兔子速度是乌龟的2倍，所以当乌龟走了T步，到底入口时，兔子在循环内走了T步。
所以H=T%L=5
之后乌龟和兔子都在这个循环里面，继续进行，我们知道由于兔子和乌龟的距离是L-H，每走一步，兔子和乌龟的距离就会缩减1.所以乌龟只要在走L-H=1步，兔子和乌龟就会相遇。这个相遇节点距离入口节点的距离是多少？（相遇节点到入口节点需要走的步数）：L-(L-H)=H （重点！）
如下图：

有了以上分析，现在我们知道了乌龟和兔子相遇的那个节点。该节点距离入口节点距离是L-H。
遗憾的是我们不知道L是多少，也不知道H是多少，我们甚至不知道T是多少。
现在我们把乌龟不动，保持在相遇节点处，兔子从起始节点开始。由于兔子跑累了，所以兔子和乌龟现在速度一样，一步一个单元格。那么这种情况下上面时候会相遇呢？
由于循环链是L。当兔子走了n*L步，乌龟的位置还是在相遇节点处，所以我们知道当兔子走了T//L步后，乌龟会回到相遇节点处，这时候兔子距离入口节点的距离是T%L！！！ 而上面我们知道，相遇到入口节点的步数是：H=T%L。
这下我们知道了，兔子距离入口节点的距离和乌龟(处在相遇节点)距离入口节点的距离的距离都是H，所以，H步之后，兔子和乌龟肯定会在入口节点处相遇！！ 这个第二次相遇的节点就是我们要找的节点！！
下面是算法的伪代码：
1）让乌龟在链表中每一步一格地移动。让兔子在链表中每一步两格地移动。

2）如果兔子找到一个空链接，则链表中没有回路，所以停止。

3）否则，当兔子赶上乌龟时，让兔子从链表的开始重新跑，每一步移动一个单元格，然后继续移动乌龟，每步一格。

4）当乌龟和兔子再次见面时，它们是在循环的开始处。

这个算法虽然很简单，但是真的从0到1的过程是非常伟大的！！ 对前人致敬！