本文主要是介绍leetcode题：287. 寻找重复数(中等）（存在环的单链表寻找环的入口点），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目描述：287. 寻找重复数（中等）
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:输入: [3,1,3,4,2]
输出: 3
说明：不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-duplicate-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、解题思路
使用快慢指针法，一个指针now走一步now= nums[now]，一个指针pre走两步pre=nums[nums[pre]]。由于数组是连续并且有重复数字，相当于有环链表（不看答案想不出来）。然后问题就转换成求链表中环的入口（相同的数字就是环的入口，因为两个下标指向同一个数字，即当走两个相同的数字往下走一步的时候它们的位置相等的。
求环的入口（这里抄了一篇原理）
这里是出处：
https://blog.csdn.net/fynjy/article/details/47440049
问题2：若存在环，如何找到环的入口点（即上图中的结点E）？
解答：如图中所示，设链起点到环入口点间的距离为x，环入口点到问题1中fast与low重合点的距离为y，又设在fast与low重合时fast已绕环n周（n>0），且此时low移动总长度为s，则fast移动总长度为2s，环的长度为r。则
s + nr = 2s,n>0 ①
s = x + y ②
由①式得 s = nr
代入②式得
nr = x + y
x = nr - y ③
现让一指针p1从链表起点处开始遍历，指针p2从encounter处开始遍历，且p1和p2移动步长均为1。则当p1移动x步即到达环的入口点，由③式可知，此时p2也已移动x步即nr - y步。由于p2是从encounter处开始移动，故p2移动nr步是移回到了encounter处，再退y步则是到了环的入口点。也即，当p1移动x步第一次到达环的入口点时，p2也恰好到达了该入口点。
步骤
1、先定义快慢指针一个指针now走一步now= nums[now]，一个指针pre走两步pre=nums[nums[pre]]。通过循环找到第一次相遇的位置。
2、定义一个新指针，从头开始next = 0；然后慢指针now和next同时一起每次走一步，直到相遇now == next。此时nums[now[就是重复的数字
三、代码
class Solution {
public:int findDuplicate(vector<int>& nums) {int pre = 0;int now = 0;now = nums[now];pre = nums[pre];pre = nums[pre];bool is_first = true;while(pre != now){//cout <<"pre="<<pre<<endl;//cout<<"now="<<now<<endl;pre = nums[pre];pre = nums[pre];now = nums[now];}//cout <<"pre="<<pre<<endl;//cout<<"now="<<now<<endl;int next = 0;while(nums[now] != nums[next]){now = nums[now];next = nums[next];//cout <<"next="<<next<<","<<nums[next]<<endl;//cout<<"now="<<now<<","<<nums[now]<<endl;}return nums[now];}
};
这篇关于leetcode题：287. 寻找重复数(中等）（存在环的单链表寻找环的入口点）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
