floyd判圈算法

问题：如何检测一个链表是否有环，如果有，那么如何确定环的起点.
要求 : 空间复杂度为O(1), 时间复杂度为O(n).

假设一个有环链表如下图: 利用floyd判圈算法可以做到下面的三件事:

1. 判断是否有环
2. 计算环的长度
3. 寻找环的起点

Paste_Image.png

1.判断是否有环

使用两个指针slow和fast。两个指针都从链表的起始处S开始。slow每次向后移动一步，fast每次向后移动两步。若在fast到达链表尾部前slow与fast相遇了，就说明链表有环。
这里可以简单的证明一下：反证法，假如没有环，那么slow永远追不上fast，那么在fast到达链表尾部前slow不会fast相遇了。若相遇了，链表就有环。

2.求环的长度

当slow和fast相遇时，slow和fast必定在环上，所以只要让一者不动，另一者走一圈直到相遇，走过的节点数就是环的长度。

3.求环的起点

如图所示，设AB=n, SA=m。设环的长度为L。
假设slow走过的节点数为i，那么有：
i = m + n + aL a为slow绕过的环的圈数。
因为fast速度为slow的两倍，所以相同时间走过的节点数为slow的两倍，所以有：
2i = m + n + bL b为fast绕过的环的圈数。
两者做差有 : i = (b-a)L。
所以可知，fast和slow走过的距离是环的整数倍。
所以有m+n=L。
所以此时让slow回到起点S，，fast仍然在B。
让两个指针以每次一步的速度往前走。
当走了m步时，可发现slow和fast正好都在A处，即是环的起点。

应用

floyd判圈算法是一个很有趣的算法，在某些题目上用处很大，比如下面这个。

给出一个数组 nums 包含 n + 1 个整数，每个整数是从 1 到 n (包括边界)，保证至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
注意事项

1. 不能修改数组(假设数组只能读)
2. 只能用额外的O(1)的空间
3. 时间复杂度小于O(n^2)
4. 数组中只有一个重复的数，但可能重复超过一次

对于这个题目

• 我首先想到的是用快速排序对数组nums进行排序，然后再对排序后的数组遍历找到重复的数，这样时间复杂度就为O（nlogn），因为快排是原址排序，所以空间复杂度为O（1）。符合题目要求

• 其次想到的是桶排序，遍历数组nums,把n放到数组nums[n-1]上，一旦发现nums[n-1] == n，就说明n重复了。这样的话时间复杂度为O（n），空间复杂度为O（1），符合要求

• 最后就是用floyd判圈算法。但是floyd判圈算法不是用于链表吗，这里是数组。没有关系，我们可以把nums数组视为静态链表。那么在静态链表中有环就意味着有nums[i] == nums[j] (i != j)，即是数组元素重复，这样就和我们的题目对上了。找到重复的数字就是找到静态链表环的起点。这样的话时间复杂度为O（n），空间复杂度为O（1），符合要求。
  下面附上代码：

public int findDuplicate(int[] nums) {
    // write your code here
   int x = 0;
    int y = 0;
    do {
        x = nums[x];
        y = nums[nums[y]];
    } while (x != y);
    
    x = 0;
    do {
        x = nums[x];
        y = nums[y];
    } while (x != y);
    return x;
}