在处理链表相关的算法问题时，你是否遇到过这样一种令人头疼的情况：程序运行了一会儿后突然卡死，或者陷入了无限循环？这往往是因为我们的链表中出现了一个隐蔽的“环”。
判断链表中是否存在环，不仅是数据结构学习中的经典关卡，更是各大技术公司面试中高频出现的考题。今天，我们将深入探讨这个问题。我们将从最直观的思路出发，逐步剖析算法的演进过程，最终掌握那个既优雅又高效的“Floyd 判圈算法”。让我们开始这场探索之旅吧。
问题描述与场景分析
首先，让我们明确一下我们在解决什么问题。
想象一下，你手里拿着一串链表节点。正常情况下，你沿着 INLINECODE64032ceb 指针一路向后走，最终会到达 INLINECODEc899886d（空节点），这标志着旅途的结束。但是，如果这串链表中存在一个“环”，情况就完全不同了：你会像走进了一个没有出口的圆圈，永远在几个节点之间打转，永远走不到尽头。
我们的目标是： 编写一个函数，传入链表的头节点，如果链表中存在环，返回 INLINECODEda2a03a6；否则返回 INLINECODEaac25d93。
这个问题在实际开发中非常具有意义。例如，在处理内存管理或缓存系统时，如果引用关系构成了死循环，就会导致内存泄漏。掌握检测环的技巧，能帮助我们写出更健壮的代码。
方法一：直观的标记法（哈希表法）
当我们面对一个“是否重复出现”的问题时，脑海中跳出的第一个念头通常是：“我需要记录下我见过的人。”
这就是我们最直观的解决思路：一边遍历链表，一边在一个笔记本（哈希表）上记录下经过的每一个节点。每到一个新节点，我们就先翻翻笔记本：“嘿，我以前见过这个节点吗？”
- 如果回答是“见过”，那么恭喜，你发现了环，因为你不应该第二次走到同一个节点。
- 如果回答是“没见过”，那就把它记下来，继续前进。
#### 算法详细步骤
- 初始化一个空的哈希集合，我们称之为
visited_nodes。 - 创建一个指针 INLINECODEa46a9631，初始指向链表的头部 INLINECODE3ce61900。
- 开启循环，只要
current不为空：
* 检查：判断 INLINECODEca3d40d7 是否存在于 INLINECODE5e410f68 中。
* 若存在，直接返回 True，环已找到。
* 记录：若不存在，将 current 加入集合。
* 移动：将 INLINECODE7df624bf 更新为 INLINECODE71836ea4，继续前行。
- 如果循环正常结束（即 INLINECODE2dbc3e2d 变成了 INLINECODEb99333e4），说明我们已经走到了尽头，并没有遇到重复节点，返回
False。
#### Python 代码实战
让我们看看如何用 Python 优雅地实现这个逻辑：
class ListNode:
"""链表节点的定义"""
def __init__(self, x):
self.val = x
self.next = None
def detect_cycle_hashing(head):
"""
使用哈希表检测链表中的环。
:type head: ListNode
:rtype: bool
"""
# 使用集合作为我们的“笔记本”，记录访问过的节点
visited_nodes = set()
current = head
while current:
# 如果当前节点已经在集合中，说明我们经过了两次，有环！
if current in visited_nodes:
return True
# 否则，记录下这个节点
visited_nodes.add(current)
# 继续向后移动
current = current.next
# 到达末尾，未发现环
return False
#### 复杂度分析
- 时间复杂度：O(n)。我们最多遍历链表一次。对于每个节点，哈希表的插入和查询操作平均只需 O(1) 的时间。
- 空间复杂度：O(n)。这是该方法的短板。在最坏的情况下（例如链表没有环，或者环在链表末尾），我们需要存储所有的 n 个节点。如果链表非常长，这会消耗相当可观的内存。
虽然这个方法直观易懂，但在面试中，面试官通常会追问：“能不能再优化一下空间复杂度呢？”这就引出了我们的第二种方法。
—
方法二：Floyd 判圈算法（龟兔赛跑）
如果你在面试中能写出了上面的哈希表解法，这已经很不错了。但如果你想展现出对算法本质的深刻理解，Floyd 判圈算法（Floyd‘s Cycle-Finding Algorithm）才是真正的“杀手锏”。
这个算法还有一个更生动的名字——龟兔赛跑算法。
#### 核心思想：为什么双指针能相遇？
想象一下那个经典的寓言故事：
- 乌龟（慢指针）：每次只走一步。
- 兔子（快指针）：每次走两步。
如果跑道（链表）是一条直线，没有终点（有环），那么跑得快的兔子会一直冲向远方，永远不会回头，当然也就追不上乌龟。但是，如果跑道是一个圆形的环，情况就变了。兔子跑得快，它最终会绕着圈跑，从后面“套圈”追上乌龟。
这就是算法的核心逻辑：如果存在环，快指针最终一定会在环内追上慢指针（即 fast == slow）。如果不存在环，快指针会先到达链表末尾。
#### 算法详细流程
- 初始化：定义两个指针 INLINECODE0348ddce 和 INLINECODE67f0974d，都指向链表头节点
head。 - 循环条件：只要 INLINECODE961805e7 不为空，且 INLINECODEc6b98fc8 的下一个节点
fast.next也不为空（保证快指针能走两步），我们就继续循环。 - 移动指针：
* INLINECODE0779fb13 每次向后移动一步：INLINECODE5dfa590c。
* INLINECODEe19af6b4 每次向后移动两步：INLINECODEcba9ee14。
- 检测相遇：在移动的过程中，检查 INLINECODE604831af 和 INLINECODE1b90fc7c 是否指向了同一个节点。
* 如果是，返回 True（检测到环）。
- 退出循环：如果循环因为 INLINECODEed9238a5 或 INLINECODEc89117d7 为 INLINECODEc51fda9d 而结束，说明链表到了尽头，返回 INLINECODE18c02393（无环）。
#### Python 代码实战
这种方法的代码实现非常简洁，但包含着巧妙的逻辑：
def detect_cycle_floyd(head):
"""
使用 Floyd 判圈算法（龟兔赛跑）检测链表中的环。
空间复杂度 O(1)，时间复杂度 O(n)。
"""
# 边界条件检查：链表为空或只有一个节点且无自环
if not head or not head.next:
return False
slow = head
fast = head
# 只要快指针还能继续跑（当前和下一个都不为空）
while fast and fast.next:
# 乌龟走一步
slow = slow.next
# 兔子走两步
fast = fast.next.next
# 检查是否相遇
if slow == fast:
return True
# 如果快指针到了尽头，说明没有环
return False
#### 深入解析：为什么一定是 O(n)？
你可能会好奇：万一兔子每次都差一点点才追上乌龟呢？会不会导致时间复杂度变得不可控？
放心，数学证明告诉我们，这种情况不会发生。
- 非环部分：假设非环长度为 $L$。慢指针进入环时，快指针已经在环里了，或者也刚进环。这部分的耗时是线性的。
- 环内部分：假设环的长度为 $C$。在环内，每一轮循环，快指针都会比慢指针多走 1 步（因为快走 2 步，慢走 1 步）。这意味着，它们之间的距离会按照 $C, C-1, C-2…$ 的速度缩减。最多经过 $C$ 次移动，它们就会相遇。
因此，总的时间复杂度依然保持在 O(n)，这是一个非常稳健的线性算法。
#### 复杂度分析
- 时间复杂度：O(n)。如上所述，我们最多遍历链表节点常数次。
- 空间复杂度：O(1)。这是此算法的巨大优势。我们只需要两个指针变量，无论链表有多长，占用的内存都是固定的。
—
进阶挑战：寻找环的入口节点
掌握了判断环是否存在，仅仅完成了任务的一半。在实际面试或算法竞赛中，经常会接着追问一个更难的问题：“如果链表有环，请找到环的入口节点。”
例如，在链表 1 -> 2 -> 3 -> 4 -> 5 -> 2（回到节点2）中，环的入口就是节点 2。
#### 算法思路的延伸
Floyd 算法不仅告诉我们有没有环，还帮我们确定了相遇点。要找到入口，我们可以利用以下数学规律（这是该算法最精妙的部分）：
- 第一阶段：使用上述的快慢指针法，找到两者在环内的相遇点（记为
meet）。 - 第二阶段：将其中一个指针（例如快指针 INLINECODEd66b68a8）重新指向链表头节点 INLINECODEa3e5f524，并将其速度降为 1 步（即也变成慢速）。
- 第三阶段：让 INLINECODE5572a1f8 从相遇点继续前行，INLINECODEb38ae8d9 从头部前行。此时，两个指针都以每次 1 步的速度移动。它们再次相遇的那个节点，就是环的入口节点。
#### Python 代码实现（寻找入口）
让我们通过代码来验证这个神奇的性质：
def detect_cycle_start_node(head):
"""
找到链表环的入口节点。
如果无环，返回 None。
"""
if not head or not head.next:
return None
slow = head
fast = head
# 第一阶段：寻找相遇点
has_cycle = False
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
has_cycle = True
break
# 如果没有环，直接返回
if not has_cycle:
return None
# 第二阶段：寻找入口
# 将 fast 重置回头部，速度变为 1
fast = head
# 此时 slow 停留在相遇点不动（或者也可以继续走，只要速度一致即可）
# 当 fast 和 slow 再次相遇时，即为入口
while fast != slow:
fast = fast.next
slow = slow.next
# 返回入口节点
return slow
这个解法非常优美，依然保持了 O(1) 的空间复杂度和 O(n) 的时间复杂度，是处理此类问题的标准答案。
—
最佳实践与常见陷阱
在实际编写这些代码时，有一些细节需要特别注意，否则很容易导致程序崩溃或逻辑错误。
1. 空指针异常
这是最容易犯错的地方。在 Floyd 算法中，快指针是“走两步”的。在写 INLINECODEd8ea94a9 之前，你必须确保 INLINECODEd0145a7e 不是 INLINECODE949f6958，且 INLINECODE31a6f856 也不是 null。
错误示范：
# 危险！如果 fast 是 None，fast.next 会报错
while fast:
if fast.next.val == ...
正确写法：
# 安全的循环条件
while fast and fast.next:
# 你的逻辑
2. 链表结构的破坏
如果使用哈希表法，虽然思路简单，但严格来说，我们不应该修改原有的节点类（比如为了省事给节点加个 visited 属性）。在实际工程中，数据结构通常是只读的，或者是线程共享的，随意修改结构可能会引发难以预料的 Bug。因此，使用外部哈希表比修改节点结构更规范。
3. 性能考量
- 哈希表法：虽然代码好写，但在极端大数据量的链表中，维护 O(n) 大小的哈希表会造成内存压力，导致 GC（垃圾回收）频繁，影响性能。
- Floyd 算法：由于没有额外的内存开销，它是处理巨型链表的首选方案。
总结与建议
在这篇文章中，我们深入探讨了检测链表环的两种主要方法，并延伸到了寻找入口节点的高级应用。
- 哈希表法：是那种“以此为此，虽慢但稳”的方法。当你卡壳时，它是最容易想到且能保证正确性的方案。
- Floyd 判圈算法：则是工程师追求极致性能的体现。它在 O(1) 的空间内完成了 O(n) 的工作，既节省内存又极其高效。
给你的建议
- 理解大于记忆：不要死记硬背“龟兔赛跑”的代码。试着想象一下那个圆环，想象两只指针在跑动，理解为什么快指针能追上慢指针。
- 动手调试：在 IDE 中实际写一段代码，构造一个带环的链表，然后打印出 INLINECODEf1462532 和 INLINECODEf5db8de6 每一步的位置。看着它们一步步相遇，你会对这个算法有更直观的感受。
希望这篇指南能帮助你彻底攻克链表成环问题。当你下次在面试中遇到这道题时，你可以自信地画出那个圆圈，并解释为什么那只“兔子”一定会追上“乌龟”。祝你编码愉快！