题目链接:287. 寻找重复数 - 力扣(LeetCode)
n+1个数的范围在[1,n],如果以值为下标作为链表指针,没有重复的数也能成环,有重复的数就是这个环有一个数可以由多个地方到达,也就是环有一个入口,这个入口就是重复的数
如:0->1->2->0,加一个重复的数指向2,那么2就是这个环的入口
用快慢指针必会在环里相遇,假设起点到入口的距离是a,入口到相遇的地方距离是b,相遇的地方到入口继续转的距离是c,如果相遇那么快指针比慢指针会多跑一圈,也就是多跑了b+c,而也多走了一倍的距离也就是a+b,那么a=c,此时让一个指针从起点跑a步会到达入口处,一个指针从相遇处跑a步也就是c步也会到达入口处,即重复的数
class Solution {
public:
int findDuplicate(vector<int> &nums) {
int slow = 0, fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
fast = 0;
while (fast != slow) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
};