floyd判圆算法及链表判环应用

• 先决条件
• floyd算法的结论
• 论证
• 287. 寻找重复数

先决条件

存在一个有向链表

两个快慢指针，快指针每次走两步、慢指针每次走一步

floyd算法的结论

1. 如果链表存在环路，那么快、慢指针将会在环内相遇
2. 如果不存在环路，那么快指针永远追不上慢指针，直至走到节点末尾。
3. 假设快、慢指针相遇，这时存在两个同速指针A、B，每次走一步，A在链表开始位置，B在相遇位置，那么A、B再次相遇就是环的入口点。

1、2两条结论其实很好理解、如果不存在环路，快的永远比慢的走的远，因为每一个周期内，快、慢指针的距离就会远离1。如果存在环路，那么快、慢指针不可能在环开始点之前相遇，和上面一样的道理，又因为快指针与慢指针的相对速度是1，那么总会在某个时间点他俩相遇。接下来我们来证明第三条结论。

论证

在证明第三条结论之前，我们需要证明其他几个结论

1. 快、慢指针第一次相遇时，慢指针从环开始点到相遇点一共走的步数小于等于环周长（走了一圈以内包含一圈）。
2. 快指针与慢指针第一次相遇时，快指针从环开始点到相遇点一定走了一圈以上的步数。

这两条结论看似不起眼，其实是我们证明的关键信息。

来头脑风暴一下，如果慢指针走到了环开始点，那么快指针的位置在哪里？可以肯定的是，快指针在环内，具体在哪个位置是不确定的，我们可以说:慢指针相对环开始点距离=0，快指针相对环开始点距离>=0。假设快指针到开始点的位置是y，环周长是c，那么c>=y>=0.因为快指针比慢指针的速度快1一个单位，那么我们假设慢指针不动，快指针速度为1，那么可以得知在c-y/Vf(1)的时间后,快指针追上了慢指针。此时慢指针走的距离是c-y。快指针走的距离是2x(c-b)。注意上面我们只是说经过c-y可以相遇，但并没有说第几次相遇，假设c-b=0，那说明慢指针走到环节点开始位置时已经第一次相遇了。这时慢指针在圈内距离是0，快指针在圈内距离是周长c，这是临界情况，即头节点到环起始点位置相等。

此时x=c,y=0,那么得知z=x;

所以我们令b>0,即c-b<c。慢指针一定没走完一圈被快指针第一次追上了，他从开始点一共走了c-y的距离,而快指针相对相遇点走了2(c-b)<2c。所以第一次相遇时，快指针走了一圈以上的距离。

有了上面两个结论，我们就可以列出来等式了，假设快指针在圈内走了n圈后与慢指针相遇,n>=1,头节点到环起始点长度x，环起始点到相遇点长度y，相遇点到起始点长度z，那么

(x + y) * 2 = x + y + n (y + z) n>=1。=> x = (n - 1) (y + z) + z，当n=1时，x=z。这就证明了第三条结论。

得出结论：

{
	当x=c时，x=z
	当x!=c时，x=z
}
=>
当快慢节点第一次相遇，有x=z.

这时我们就可以看这道题了

287. 寻找重复数 (opens new window)

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2] 输出：2 示例 2：

输入：nums = [3,1,3,4,2] 输出：3

提示：

1 <= n <= 105 nums.length == n + 1 1 <= nums[i] <= n nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

寻找重复数，其实就是寻找链表环的头节点。

int findDuplicate(int* nums, int numsSize){
    int temp;
    while(nums[0]!=nums[nums[0]])
    {
        temp=nums[nums[0]];
        nums[nums[0]]=nums[0];
        nums[0]=temp;
    }
    return nums[0];
}