链表环

判断链表是否有环以及找到环的位置的通用做法就是快慢指针，在探讨具体的算法前，我们先了解下面的基础知识，当然你也可以去阅读维基百科 Floyd判圈算法。

知识点1

存在一个环，环的大小为n，有两个指针p1, p2, p1每次在环内可以移动一步，p2在环内 每次可以移动两步, p1和p2必然在链表的某一个位置相遇，证明如下：

详细证明

设环长度为 $n$ ( $n \geq 1$)，不失一般性，假设两个指针在环中初始位置分别为 $p1$ 和 $p2$。由于环是循环的，我们可以将位置表示为模 $n$ 的整数。

定义：

• $s_t$：慢指针在时间 $t$（经过 $t$ 次移动）时的位置 $s_t \equiv s_0 + t \pmod{n}$ , 其中 $s_0$ 是初始位置。

• $f_t$：快指针在时间 $t$ 时的位置 , $f_t \equiv f_0 + 2t \pmod{n}$ 其中 $f_0$ 是初始位置。

相遇条件推导

两指针相遇的条件是 $s_t \equiv f_t \pmod{n}$，即：

$$s_0 + t \equiv f_0 + 2t \pmod{n}$$

移项得：

$$\begin{align*} t - 2t &\equiv f_0 - s_0 \pmod{n} \\ \\ -t &\equiv d_0 \pmod{n} \end{align*}$$

其中 $d_0 = f_0 - s_0$ 是初始时快指针相对于慢指针的顺时针距离$0 \leq d_0 < n$，因为模 $n$ 下距离取最小值）。

等价形式

上式可重写为：

$$t \equiv -d_0 \pmod{n}$$

或等价地：

$$t \equiv n - d_0 \pmod{n} \quad \left(\text{因为} \quad -d_0 \equiv n - d_0 \pmod{n}\right)$$

通解与特解

这意味着当 $t = k \cdot n - d_0$（其中 $k$ 为某个非负整数）时，两指针相遇。由于 $0 \leq d_0 < n$，我们可以取 $k=1$（或最小非负整数），得到：

$$t = n - d_0$$

因为：

• 若 $d_0 = 0$ → $t = n$（绕环一周后相遇）
• 若 $d_0 > 0$ → $0 < t \leq n$（$d_0 = n-1$ 时 $t = 1$

$\therefore$ 在 $t \leq n$ 步内，两指针必然相遇。

知识点2

当链表存在环时，通过快慢指针求出两个指针相遇的点，然后将慢指针重新设置为链表头，然后以相同步长为1的速度使两个指针前进
两个指针再次相遇时，就是这个环路在链表中的起点。这里不在赘述这个证明过程。

应用1

寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

这道题可以利用判圈算法来解决这个题是空间和时间最优的算法。这里有个非常关键的点就是需要构造节点间的关系：

构造 数组下标 i -> nums[i]的 映射关系，这样一定会出现环，且重复元素从0号下标开始的链表里面，这里做一个简单的证明：

1. 通过这个构造方式，我们知道，[0, n]这个范围内的所有的值都有一个对应的数，意味着这 n + 1 个节点，每个节点都有一个出边，因为数组范围有限，不能无限延申，要满足这个条件，链表必须要有环，这样我们知道了通过这种构造方式，一定会出现m个环包含了所有元素(环可以是自包含，但是不存在出度为0的结点)；
2. 为什么重复元素一定在以0开头的链表里面？我们想一下，如果链表不存在重复元素，且构成一个环，那么这个环一定是首尾相连的，不然必然出现一个节点入度大于2，那么这个环里一定有重复元素，而我们知道，不可能有元素指向0，所以这个链表一定不是首尾相连，一定会出现入度大于2的一个元素，根据我们的构造方式，这就意味着有两个下标的映射值相等，即等价于这个链表有重复元素；

结合知识点1 和 知识点 2，写出如下代码

展开代码

#include <bitset>
#include <vector>

using namespace std;
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int fast = 0;
        int slow = 0;
        // 1. 寻找环中相遇位置
        do {
            slow = nums[slow];
            fast = nums[fast];
            fast = nums[fast];
        } while (fast != slow);
        
        // 2. 重置慢指针，找到环入口
        slow = 0;
        while (fast != slow) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};