---
# System prepended metadata

title: Algo｜Floyd's cycle detection 演算法
tags: [Algo]

---

# Floyd's cycle detection 演算法
- 檢測一個 linked list 中是否有環
    - 若`起點到 cycle 起點`距離為 x，`cycle 起點到碰面點`距離為 y
    - -> 可推得 x+y 為環的長度的倍數
    - -> 從碰面點走 x 可以回到 cycle 起點
    ```clike=
    void solve(){
        struct Node *slow = a, *fast = a;
        while(fast->next && fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)    break;
        }
        if(fast->next == NULL || fast->next->next == NULL){
            cout<< "There is no cycle\n";
            return;
        }
        
        slow = a;
        while(slow != fast){
            slow = slow->next;
            fast = fast->next;
        }
        cout << "Cycle starts at node " << slow->data << "\n";
        return;
    }
    ```
- [287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)
    ```clike=
    void findDuplicate(vector<int>& nums){
        int n = nums.size();
        
        int slow = nums[0], fast = nums[nums[0]];
        while(slow != fast){
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        
        slow = 0;
        while(slow!=fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
    ```


