Floyd龟兔赛跑算法，用来解决链表中环的问题，leetcode链接
理论证明
首先兔子一次走两步，乌龟一次走一步。在若干次后，如果链表有环，他们一定会相遇。证明如下：
（显然的问题，当他们进入环以后，快指针每次移动都是向慢指针靠近一个位置）
在相遇过后，由于乌龟走的长度可以被证明是环长的整数倍.证明如下：
设从链表开头到环的开头的距离是k，环的长度为n，他们第一次相遇的时候，在环上走的长度(小于n的那个)设为m，则可以这样表示：
兔子走的长度为：k+n*i(i为一个未知的正整数)+m ①
乌龟走的长度为：k+n*j(j为一个比i小的未知的正整数)+m ②
这样式①—式②可得，乌龟走的长度为：n(i-j)，又n*(i-j)=m+k+j\n (式②)—>这里化简左右式，可以得到，m+k一定是n的倍数
❗注意，这里相减可以得到的原因是由于兔子走的长度是乌龟走的2倍
接着让乌龟回到起点开始走，兔子一次走一步。这样当他们再次相遇的时候，他们的相遇的点就是链表中环的起点。证明如下：
剩下的长度为(m+k)%n一定为0，设m+k=ni。k=n\i-m
当乌龟走了k步时，乌龟到达了环的起点，兔子也走了k步，这个时候兔子的相对位置x= k+m(m为他们相遇的地方)=n*i—>兔子这个时候也是在环的起点。
ℹ️兔子一次走3步，可能就不会相遇了，很简单的设想相对速度为2，如果他们初始相差距离不是2的倍数，比如9，那么永远都不会相遇，很多人把Floyd算法和跑步类比，这是完全错误的，因为它一次走了固定的距离，而并非连续。就好像我们说芝诺的乌龟悖论一样，实际上从数学极限的角度来说，虽然会有无限多个步骤，但最终如果固定时间的话，距离会收敛。
代码实现
对于lc141，和lc142，都是一样的，我这里使用两种方法解决
public class DetectCycle {
/**
* 找出环形链表的第一个头结点
* 1：使用Floyd算法，数学证明第一次相遇必定在环这里
* 2：使用HashSet，遇到重复的节点就说明找着了
**/
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (true) {
// 链表暂时没有环，只需要判断fast即可
if (fast == null || fast.next == null) {
return null;
}
// 链表可能有环
// 移动指针
slow = slow.next;
fast = fast.next.next;
// 找到链表入口
if (slow == fast) {
break;
}
}
// 接下来从起点重新开始，一次走一步
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
/**
* 判断链表是否有环，跟前面那个快慢指针一模一样，找到交接点直接return就可以了。这里使用HashSet
**/
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
HashSet<ListNode> set = new HashSet<>();
ListNode curr = head;
while (true) {
if (curr.next == null) { // next==null就说明没环了
break;
}
if (set.contains(curr)) { // 发现有相同的了
return true;
} else { // 正常遍历
set.add(curr);
curr = curr.next;
}
}
return false;
}
}