//Basically transfer the problem to finding the beginning of cycle in linked list.
public int findDuplicate(int[] nums) {
if(nums.length ==0 )
return 0;
int slow=0, fast=0;
slow = nums[slow];
fast = nums[nums[fast]];
while(slow != fast){
if(slow == nums[slow])
return slow;
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0;
while(slow != fast){
if(slow == nums[slow])
return slow;
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
O(N) without extra space & without modifying the array


//Can be further simplified.
public int findDuplicate(int[] nums) { if(nums.length ==0 ) return 0; int slow=0, fast=0; slow = nums[slow]; fast = nums[nums[fast]]; while(slow != fast){ slow = nums[slow]; fast = nums[nums[fast]]; } fast = 0; while(slow != fast){ slow = nums[slow]; fast = nums[fast]; } return slow; }

good idea. what we need to find is the node which is the previous node of the node which is the entrance of the ring.
int FindDuplicateNumber::findDuplicateCyclicList(vector<int> &nums) {
if(nums.size() ==0 )
return 0;
int slow =0;
int fast =0;
slow = nums[slow];
fast = nums[nums[fast]];
while(slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
int iDesiredLatter = slow;
while (nums[slow] != iDesiredLatter){
slow = nums[slow];
}
return slow;
}