环形链表系列导学

问题描述

给定一个单链表,可能存在一个环。我们的目标是找到环的入口节点,即从这个节点开始,链表进入循环。如果没有环,则返回 null。

将链表问题转化为数学问题

状态序列与循环

我们可以将链表节点视为状态,每个节点的 next 指针代表状态转移函数 $f$。从头节点开始,我们可以得到一个状态序列:

• $x_0,x_1=f(x_0),x_2=f(x_1),x_3=f(x_2),\dots$

如果链表中存在环,那么这个序列将出现循环。

寻找循环起点

我们的目标是找到状态序列中最小的 $\mu$,使得对于某个最小的 $\lambda$,满足:

• $x_{\mu }=x_{\mu +\lambda }$

其中:

• $\mu$ 是循环的起始位置(环的入口)
• $\lambda$ 是循环节的长度(环的长度)

Floyd 判圈算法的数学原理

阶段一：检测循环

使用两个指针:

• 慢指针(slow)：每次移动一步
• 快指针(fast)：每次移动两步

阶段二：找到循环的起始位置

数学推导

设:

• 非环部分长度：$a$
• 环的长度：$b$
• 从环入口到相遇点的距离：$c$
• 快指针在环内绕行的圈数：$k$ ($k\ge 1$)

距离关系

• 慢指针走的总距离：
  $D_{\text{slow}}=a+c$

• 快指针走的总距离：
  $D_{\text{fast}}=a+c+k\times b$

• 由于快指针速度是慢指针的两倍：
  $D_{\text{fast}}=2\times D_{\text{slow}}$

推导步骤

1. 建立等式：
   $a+c+k\times b=2\times (a+c)$

2. 化简：
   $a+c+k\times b=2a+2c$
   $k\times b=2a+2c-a-c$
   $k\times b=a+c$

3. 得出关系式：
   $a+c=k\times b$

寻找环的入口

• 快指针走了 $a$ 步到达环入口
• 慢指针从相遇点再走 $b-c$ 步也到达环入口

因为:
$b-c=b-(k\times b-a)=-(k-1)\times b+a$

具体例子

假设:

• 非环部分长度：$a=3$
• 环的长度：$b=4$
• 快指针在环内绕行的圈数：$k=1$

根据推导:
$a+c=k\times b⟹c=k\times b-a=1\times 4-3=1$

• 慢指针走的总距离：
  $D_{\text{slow}}=a+c=3+1=4$

• 快指针走的总距离：
  $D_{\text{fast}}=2\times D_{\text{slow}}=8$

验证快指针的距离:
$D_{\text{fast}}=a+c+k\times b=3+1+1\times 4=8$