为何「数组中寻找重复数」问题的数组可转化为带环链表？

明确问题约束 #

给定长度为n+1的数组nums，所有元素取值范围为[1,n]，且仅有一个重复数（重复次数≥2），要求不修改数组、用常数空间找到这个重复数。

证明：该数组必然对应带环结构 #

我们可以把数组转化为一个函数映射关系：对每个索引i，定义函数f(i) = nums[i]。

• 数组元素的取值范围是[1,n]，而数组的索引范围是0~n（共n+1个）。
• 从索引0出发，生成序列：0 → nums[0] → nums[nums[0]] → nums[nums[nums[0]]] → ...。这个序列的每一项都是合法索引，但序列是无限的，而索引的可能值只有n+1个。根据鸽巢原理，必然存在某个索引被重复访问，一旦重复，就意味着序列进入了循环，也就是形成了环。

环的入口就是重复数 #

假设重复数是x，那么至少存在两个不同的索引i≠j，使得nums[i] = nums[j] = x。

• 在映射关系里，这意味着f(i)=x、f(j)=x——也就是两个不同的"节点"都指向x，说明x是环的入口：从i或j出发都会进入以x为起点的环，而从0到x的路径是无环的链，到达x后就会进入循环。
• 进一步看，x的映射f(x)=nums[x]，继续迭代下去最终一定会回到x，因为整个序列必然有环，而x是被多个节点指向的唯一节点，所以它就是环的入口。

和带环链表的等价性 #

把每个索引看作链表的节点，f(i)=nums[i]看作节点i的next指针指向节点nums[i]，那么整个结构就完全等价于一个带环链表：

• 节点0是链表的起点，沿着next指针遍历，最终会进入一个环，环的入口节点就是我们要找的重复数。

这就是为什么Floyd循环查找算法（快慢指针）可以直接应用在这个问题上——它的逻辑和链表找环完全一致。

内容的提问来源于stack exchange，提问作者Emiya Elien