...
至此，问题转换为 142 题。那么针对此题，快、慢指针该如何走呢。根据上述数组转链表的映射关系，可推出
142 题中慢指针走一步 slow = slow.next ==> 本题 slow = nums[slow]
142 题中快指针走两步 fast = fast.next.next ==> 本题 fast = nums[nums[fast]]
...
这只是一个巧合吗, 我们来分析一下
- 假设入环之前的长度为
L, 入环之后快慢指针第一相遇时快指针比慢指针🐢多跑了N圈, 每一圈的长度为C, 此时快指针🐰在环内离入环节点的距离为C' - 此时慢指针🐢走过的距离为:
L + C' - 此时快指针🐰走过的距离为:
L + C' + N * C - 因为快指针🐰的速度是慢指针🐢的两倍, 所以有:
2 * (L + C') = L + C' + N * C - 整理后得到:
(N - 1) * C + (C - C') = L - 由此可知, 若此时有两个慢指针🐢同时分别从链表头结点和快慢指针第一次相遇的节点出发, 两者必然会在入环节点相遇
代码实现
| Code Block | ||
|---|---|---|
| ||
class Solution {
public int findDuplicate(int[] nums) {
int slow = 0;
int fast = 0;
slow = nums[slow];
fast = nums[nums[fast]];
while(slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
int pre1 = 0;
int pre2 = slow;
while(pre1 != pre2){
pre1 = nums[pre1];
pre2 = nums[pre2];
}
return pre1;
}
} |
...