Slow-Fast Pointers（Floyd's cycle-finding algorithm）

Application:

1. Detect cycle on Directed Graph
2. Find the duplicate number (O(n))
3. Finite State Machine
4. Linked List Cycle

Linked List Cycle II

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;

    while (fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;

        if (fast == slow){
            ListNode slow2 = head; 
            while (slow2 != slow){
                slow = slow.next;
                slow2 = slow2.next;
            }
            return slow;
        }
    }
    return null;
}

Find the Duplicate Number

Solution：

• Pigeonhole principle（加强版二分法）

  1. 二分法主要的思想是，当前集 --> 结果集 的过程中可以把一半结果一定不在当中情况删除，从而进一步把范围缩小一半达到O(logN)的情况
  2. 用下标来表示整个数组的数字！
     • 我们比较的mid而不是nums[mid]
     • 因为mid是下标，所以判断式应为cnt > mid，最后返回min
  3. 从中间任意找一点分开之后，按照pigeonhole Principle /pi'geon/ ，我们需要遍历其中一半，count 有多少个数字小于等于中间数字。如果总数大于中间数字判断重复结果应该是在左，反则在右。

public int findDuplicate(int[] nums) {
    int min = 0, max = nums.length - 1;
    while(min <= max){
        // 找到中间那个数
        int mid = min + (max - min) / 2;
        int cnt = 0;
        // 计算总数组中有多少个数小于等于中间数
        for(int i = 0; i < nums.length; i++){
            if(nums[i] <= mid){
                cnt++;
            }
        }
        // 如果小于等于中间数的数量大于中间数，说明前半部分必有重复
        if(cnt > mid){
            max = mid - 1;
        // 否则后半部分必有重复
        } else {
            min = mid + 1;
        }
    }
    return min;
    }

• Floyd's cycle-finding

  1. 我们先用快慢两个下标都从0开始，快下标每轮映射两次，慢下标每轮映射一次，直到两个下标再次相同。
  2. 这时候保持慢下标位置不变，再用一个新的下标从0开始，这两个下标都继续每轮映射一次，当这两个下标相遇时，就是环的起点，也就是重复的数。

public int findDuplicate(int[] nums) {
    int slow = nums[0];
    int fast = nums[nums[0]];

    while(slow != fast){
        slow = nums[slow];
        fast = nums[nums[fast]];
    }

    fast = 0;

    while(slow != fast){
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}