# Floyd's cycle detection
## 步驟
1. 龜兔同時從起點出發，兔的速度是龜的兩倍，若兩者相遇代表有 cycle 存在。
2. 第一次相遇後，龜回到起點，兔在原地。
3. 龜兔同時出發，但這次速度相同，兩者相遇的地點即是 cycle 開始處。

## 證明

假設龜速 = 1，兔速 = 2，開頭到 cycle 的距離 = m，cycle 長度 = r
第一次相遇時龜走了 k 步，兔走了 2k 步。
$$
k = m + ar + x
\\
2k = m + br + x
$$
x 代表從 cycle 起始處到相遇位置的距離，a、b 是正整數。
$$
k = (b - a) \times r
$$
代表 k 是 r 的正整數倍。
所以可以得出
$$
k = m + ar + x = (b - a) \times r
\\
m + x = (b - 2a) \times r
$$
(b - 2a) 一樣也是正整數，所以當龜從頭開始，而兔從第一次相遇處一起走同樣速度，第二次相遇的點就會是 cycle 開始處。
(以龜的觀點來看是 m，以兔的觀點來看是 $m + br + x + m = m + (2b-2a) \times r$)

## 應用在 Leetcode 287. Find the Duplicate Number

這題也可以看做是一個具有 cycle 的 list，因為 array 中的值會跳到下一個值，並且除了一個數以外都不會重複。而重複的那個數正是 cycle 的開始處，因為有兩個以上的位置會跳到同一個值。

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