龟兔赛跑算法

最近在刷leetcode的时候又刷到一道链式结构中的环问题，具体问题见：https://leetcode-cn.com/problems/find-the-duplicate-number/

简短概述一下，就是一个大小为n+1的数组中，每个元素的大小范围为[1,n]，该数组有且仅有一个重复数字，找出这个重复数。

限制条件为：

• 时间小于O()
• 额外空间为O(1)

下面先介绍龟兔赛跑算法。龟兔赛跑算法又称Floyd判圈算法，顾名思义是用来判断链式结构中的环，其具体的作用包括：

1. 判断链表中是否有环
2. 如果链表中有环，求出环的长度
3. 找到环的起点

算法描述

1.判断是否有环

初始状态下，假设起点为S，以及两个在起点位置的龟兔指针分别用slow和fast来表示，让slow与fast同时向前进，同时fast的速度为slow的两倍。若fast不再前进，说明遇到了一个没有后继的节点即不存在环；否则，如果slow与fast相遇，则存在环。

fast,slow = start
while(fast.next!=null&&fast.next.next!=null){
  slow = slow.next;
  fast = fast.next.next;
  if(fast==slow) have_circle();
}

2.求环的长度

接上一步，如果判断链表中存在环，即slow与fast相遇，说明此时slow与fast皆在环内。此时只需让其中一个指针保持不动，然后让另外一个指针继续向前进，当再次相遇则说明走了一圈，即为环长。

count = 1;
fast = slow.next;
while(fast!=slow){
  fast = fast.next;
  count++;
}

3.求环的起点

还是接第一步，让slow保持与fast相遇的位置不动，然后让fast从S再次出发，此时让fast的速度与slow保持一致，同时前进，当再次相遇的时候，则为环的起点。看到这里大家肯定一脸懵逼了，下面给出证明：

• 假定S距离环起点距离为m，环的周长为n，（第一次）相遇点距离环的起点的距离是k。那么当两者相遇时，慢指针（slow）移动的总距离i = m + a * n + k，快指针（fast）的移动距离为2i，2i = m + b * n + k。其中，a和b分别为slow和fast在第一次相遇时转过的圈数。让两者相减（快减慢），那么有i = (b - a) * n。即i是圈长度的倍数。
• 将一个指针移到出发起点S，另一个指针仍呆在相遇节点M处两者同时移动，每次移动一步。当第一个指针前进了m，即到达环起点时，另一个指针距离链表起点为i + m。考虑到i为圈长度的倍数，可以理解为指针从链表起点出发，走到环起点，然后绕环转了几圈，所以第二个指针也必然在环的起点。即两者相遇点就是环的起点。

fast = S;
while(fast!=slow){
  fast = fast.next;
  slow = slow.next;
}

再回到之前讲的这道题，虽然给定的是数组，但是可以发现，题中所给数组可以看成链表（不一定是一条链），其中下标为节点地址，元素值为下一节点地址next。由于每个节点都有下一节点，即next都不为空，故链表一定有环。

由于元素范围为[1, n]，故下标为0的节点nums[0]不会作为其他节点的下一节点next，因此从0节点开始的链表中一定会存在两个节点的next相同，这个next即为要找的出现两次以上的元素，也就是链表中环的起点。直接套用龟兔算法即可。

完整Java代码如下：

    public int findDuplicate(int[] nums) {
        int slow=0,fast=0;
        while(true) {
            slow = nums[slow];
            fast = nums[fast];
            fast = nums[fast];
            if(fast==slow)break;
        }
        fast = 0;
        while(slow!=fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }

参考文章：
https://www.jianshu.com/p/a388d91141af
https://blog.csdn.net/u012482487/article/details/49798169