环形链表系列导学
问题描述
给定一个单链表,可能存在一个环。我们的目标是找到环的入口节点,即从这个节点开始,链表进入循环。如果没有环,则返回 null。
将链表问题转化为数学问题
状态序列与循环
我们可以将链表节点视为状态,每个节点的 next 指针代表状态转移函数
f
f
f。从头节点开始,我们可以得到一个状态序列:
- x 0 , x 1 = f ( x 0 ) , x 2 = f ( x 1 ) , x 3 = f ( x 2 ) , … x_0, x_1 = f(x_0), x_2 = f(x_1), x_3 = f(x_2), \ldots x0,x1=f(x0),x2=f(x1),x3=f(x2),…
如果链表中存在环,那么这个序列将出现循环。
寻找循环起点
我们的目标是找到状态序列中最小的 μ \mu μ,使得对于某个最小的 λ \lambda λ,满足:
- x μ = x μ + λ x_{\mu} = x_{\mu + \lambda} xμ=xμ+λ
其中:
- μ \mu μ 是循环的起始位置(环的入口)
- λ \lambda λ 是循环节的长度(环的长度)
Floyd 判圈算法的数学原理
阶段一：检测循环
使用两个指针:
- 慢指针(slow)：每次移动一步
- 快指针(fast)：每次移动两步
阶段二：找到循环的起始位置
数学推导
设:
- 非环部分长度： a a a
- 环的长度： b b b
- 从环入口到相遇点的距离： c c c
- 快指针在环内绕行的圈数： k k k ( k ≥ 1 k \geq 1 k≥1)
距离关系
-
慢指针走的总距离：
D slow = a + c D_{\text{slow}} = a + c Dslow=a+c -
快指针走的总距离：
D fast = a + c + k × b D_{\text{fast}} = a + c + k \times b Dfast=a+c+k×b -
由于快指针速度是慢指针的两倍：
D fast = 2 × D slow D_{\text{fast}} = 2 \times D_{\text{slow}} Dfast=2×Dslow
推导步骤
-
建立等式：
a + c + k × b = 2 × ( a + c ) a + c + k \times b = 2 \times (a + c) a+c+k×b=2×(a+c) -
化简：
a + c + k × b = 2 a + 2 c a + c + k \times b = 2a + 2c a+c+k×b=2a+2c
k × b = 2 a + 2 c − a − c k \times b = 2a + 2c - a - c k×b=2a+2c−a−c
k × b = a + c k \times b = a + c k×b=a+c -
得出关系式：
a + c = k × b a + c = k \times b a+c=k×b
寻找环的入口
- 快指针走了 a a a 步到达环入口
- 慢指针从相遇点再走 b − c b - c b−c 步也到达环入口
因为:
b
−
c
=
b
−
(
k
×
b
−
a
)
=
−
(
k
−
1
)
×
b
+
a
b - c = b - (k \times b - a) = - (k - 1) \times b + a
b−c=b−(k×b−a)=−(k−1)×b+a
具体例子
假设:
- 非环部分长度： a = 3 a = 3 a=3
- 环的长度： b = 4 b = 4 b=4
- 快指针在环内绕行的圈数： k = 1 k = 1 k=1
根据推导:
a
+
c
=
k
×
b
⟹
c
=
k
×
b
−
a
=
1
×
4
−
3
=
1
a + c = k \times b \implies c = k \times b - a = 1 \times 4 - 3 = 1
a+c=k×b⟹c=k×b−a=1×4−3=1
-
慢指针走的总距离：
D slow = a + c = 3 + 1 = 4 D_{\text{slow}} = a + c = 3 + 1 = 4 Dslow=a+c=3+1=4 -
快指针走的总距离：
D fast = 2 × D slow = 8 D_{\text{fast}} = 2 \times D_{\text{slow}} = 8 Dfast=2×Dslow=8
验证快指针的距离:
D
fast
=
a
+
c
+
k
×
b
=
3
+
1
+
1
×
4
=
8
D_{\text{fast}} = a + c + k \times b = 3 + 1 + 1 \times 4 = 8
Dfast=a+c+k×b=3+1+1×4=8