尾部带环链表快慢指针的追赶问题——使用逻辑简洁解决

​​

​ 如图有这样一个带环的单链表

(1). 可以用怎样的方法来判断链表中是否有环？                                                                    (2). 怎样返回他环形链表的起始点？                                                                                             



(1). 可以用怎样的方法来判断它是一个带环的链表？

使用快慢指针，如果最后快指针追赶上了慢指针，则代表它是一个带有环形链表的链表，如果快指针遇到了 NULL 则代表他没有环形链表。

 ※※※ 但是万一快指针太快，在多格跳跃时刚好越过了慢指针导致了死循环怎么办？※※※

    我们先简化一下环境，直接假设两个指针经过一定回合后都已经进入了环状链表。并且因为整个链表的长度都未知，我们不知道。当慢指针进入环状链表后，快指针究竟走到了哪里，所以我们先假设它们可以出现在环形链表的任何地方。

我们先从最简单的开始想，假设最开始快指针走两格，慢指针走一格开始想。这时他们俩之间的相对速度为1，也就是说无论他们之间相距多少格(假设x格)，快指针都能在 X个回合后与慢指针相遇。

    接下来有意思的就要来了，如果快指针走两格，慢指针走一格，但他们之间的距离却为奇数，那么快指针就会在第1轮刚好越过慢指针，但是这并不能说明他们俩不会相遇，毕竟他们在一个环状链表里，这时我们就要讨论环状链表节点数的奇偶，如果环状列表的节点数为奇数，那么他们在第1轮刚好错过后，他们之间的距离就会刚好 奇数-1，成为偶数，这样他们在第2轮就能刚好相遇，但如果环状链表节点数刚好为偶数，那么之后的每一轮错过，都会让他们之间的距离再次变成偶数-1，成为奇数再次错过。

举个例子：慢指着每次向前走一格，快指针每次向前走三格，慢指针初始在2号位，快指针初始在1号位 (距离为奇数)，并且他们正处于一个具有4节点个(节点数为偶数)的环形列表中，这时就会有下图

这的确是死循环了。

但是！

让我们分析一下，对于造成 “快三慢一” 的这个死循环，他需要同时满足两个要素：

① 慢指针进入环形链表时，它与快指针的距离差 N 为奇数。 ② 整个环形链表的总结点数 C 为偶数。

我们上面出现的死循环，是我们假设出的这两个要素都同时出现时的情况，但他们真的能同时出现吗？

对于 “快三慢一” 我们可以有简单的逻辑给大家证明一下：（字有点丑大家见笑了，）

所以我们刚才举出的死循环的例子不可能存在。

其实不只是 “快三慢一”，对于任意两个快慢指针，无论快指针有多快，只要是在同一出发点的带环链表中，他们俩都终将相遇，证明我放在结尾了，是数学方法证明的，大家有兴趣可以等会去结尾看。 

(2). 怎样返回他环形链表的起始点？

让快指针每次走两格，慢指针每次走一格，将他们初次的相遇点保留，再创建一个指向头部的指针，让他们同时行动每次走一格，最终相交的点，就是环形链表的初始点。

该方法，只对有以上条件的快慢指针 (快指针走两格，慢指针走一格) 走出的相遇点有效。

证明如下：

※※为什么快慢指针必须是 "快二慢一" ※※

如果仔细列过等式就会发现，如果换成 "快三慢一" 的话式子就变成了：

                                          L = 1/2(x-1)C - N 

这里的1/2，有可能就让 (x-1)C (走过的圈数) 多出半圈，半圈的话，就不能将他去掉，最后就可能导致头指针走完 L 到达环表初始点，而相遇指针却走到了环表初始点的对面(1/2环处)。其他的都和这个相似。

尾部带环链表快慢指针的相遇证明

当B进入环状链表的时间 Tb​（单位为秒）时，定义以下参数：

• Tb​ 是B到达入口的时间，满足 Vb​⋅Tb​=S（因为B刚好移动 S 格到达入口）。
• A在 Tb​ 时的位置：A的总移动距离为 Va​⋅Tb​，其中直线段长度为 S，因此A在环形跑道上的额外移动距离为 Va​⋅Tb​−S。A在环形中的位置 N（以入口为参考点，0点）满足 N=(Va​⋅Tb​−S)modC，且 0≤N<C。这里，N 表示B进入时A在环形中领先B的顺时针距离。

在环形跑道中，以 Tb​ 为时间零点（即 τ=0），A和B的位置分别为：

• A的位置： (N+Va​⋅τ)modC
• B的位置： (0+Vb​⋅τ)modC

A和B在同一格相遇的条件是存在某个 τ≥0（整数）使得：

(N+Va​⋅τ)modC=(Vb​⋅τ)modC

等价于：

N+Va​⋅τ≡Vb​⋅τ(modC)

整理得：

(Va​−Vb​)⋅τ≡−N(modC)

令 D=Va​−Vb​>0（速度差，整数），则方程变为：

D⋅τ≡−N(modC)

该线性同余方程有解的条件是 gcd(D,C) 整除 −N（即整除 N，因为整除性忽略符号）。

代入 N=(Va​⋅Tb​−S)modC，并利用 S=Vb​⋅Tb​，

有：

Va​⋅Tb​−S=Va​⋅Tb​−Vb​⋅Tb​=(Va​−Vb​)⋅Tb​=D⋅Tb​

因此：

N=(D⋅Tb​)modC

代入方程：

D⋅τ≡−(D⋅Tb​)(modC)

移项得：

D⋅τ+D⋅Tb​≡0(modC)

即：

D⋅(τ+Tb​)≡0(modC)

令 g=gcd(D,C)，并将 D 和 C 分解为 D=g⋅D′ 和 C=g⋅C′，其中 gcd(D′,C′)=1。方程变为：

g⋅D′⋅(τ+Tb​)≡0(modg⋅C′)

除以 g（因为 g>0）：

D′⋅(τ+Tb​)≡0(modC′)

由于 gcd(D′,C′)=1，这等价于：

τ+Tb​≡0(modC′)

即：

τ≡−Tb​(modC′)

由于 C′=C/g>0，且 Tb​ 为整数，该同余方程总有正整数解 τ。具体地，存在整数 k≥⌈Tb​/C′⌉ 使得 τ=k⋅C′−Tb​≥0，满足条件。因此，方程总有解，意味着A和B在某个时间点 τ>0（或 τ=0 如果当时已相遇）会在同一节相遇。

结论

在给定的离散整数条件下（所有数据为整数，速度恒定，环状链表固定），A和B最终会在同一节相遇。这是因为速度、进入时间和环形长度的整数约束导致相遇方程始终有解，无论参数的具体值如何。

以上

就是我关于环形链表两个问题的解决方法和具体思路，有理论的支撑，我们只需要几行代码就能解决这些问题。

我第一次写博客，如果有什么写的不对的或不充分的地方，欢迎指正，有其他想法的，欢迎在评论区交流。