Treat as A Linked List with circle

According to the length of nums is n + 1, and integer range is [1, n], so we can treat each element as a index that point to some next value. For example:

[1,3,4,2,2]

It can be treated as(format is element(index)):

1(0) -> 3(1) -> 2(3) -> 4(3) -> 2(4) -> 4(3)

We can see there is a circle in it, so:

class Solution {
public:
	int findDuplicate(vector<int>& nums) {
		int slow = nums[nums[0]]; // 1 step
		int fast = nums[slow]; // 2 steps
		while (slow != fast) {
			slow = nums[slow]; // 1 step
			fast = nums[nums[fast]]; // move 2 steps
		}
		slow = nums[0]; // put tortoise back to beginning.
		while (slow != fast) {
			slow = nums[slow];
			fast = nums[fast];
		}
		return slow;
	}
};