Array

将 Array 看成是 LinkedList，即 node = i & node.next = nums[i]

287 Find the Duplicate Number

根据题意，values in nums are from 1 to n. So if we traverse from value to value, then it could be infinite. So there must exist a cycle. Besides, because 0 cannot appear as a value in nums, nums[0] cannot be part of the cycle. So we start from nums[0].

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