287. Find the Duplicate Number

nums has n + 1 integers, each in [1, n], and exactly one value repeats (possibly many times). Return the repeated value without modifying nums and with O(1) extra space.

Treat i → nums[i] as a linked list. Two indices point to the duplicate value, so the list has a cycle whose entrance is the duplicate. Find it with tortoise and hare.

1function findDuplicate(nums: number[]): number {
2  let slow = 0, fast = 0;
3  do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow !== fast);
4  let p = 0;
5  while (p !== slow) { p = nums[p]; slow = nums[slow]; }
6  return p;
7}