高频必考！环形链表：为什么快慢指针永远能相遇？

LeetCode 141「环形链表」，Easy 难度，几乎人人都会写 while fast and fast.next。
但面试官根本不满足于此，真正的夺命三连问是：

• 「为什么步长选 2 和 1？选 3 和 1 行不行？」
• 「怎么证明它们一定相遇，而不是永远错过？」
• 「如果让你找环的入口，怎么改代码？」

如果你只会背代码，这篇文章就是为你准备的。

「这里不只教你怎么AC，更教你怎么在面试官面前把Floyd判圈算法的数学原理讲得清清楚楚。」

📦 题目速览（30 秒读懂）

给定一个链表的头节点head，判断链表中是否有环。

「示例：」[3,2,0,-4]，尾部连接到索引 1（值为 2）→ 返回true
「示例：」[1]，尾部指向null → 返回false

「进阶要求：」 用 「O(1)」 空间复杂度解决（即不能用哈希表存访问记录）。

🧠 核心思路：从“空间换时间”到“龟兔赛跑”

常规解法有什么问题？

visited = set()while head:    if head in visited: return True    visited.add(head)    head = head.nextreturn False

O(n) 时间，O(n) 空间。面试官会问：“如果链表有 10 万个节点，内存扛不住怎么办？”

如何优化到 O(1)？—— 追及问题

想象两个人围着环形跑道跑步：

• 「乌龟（慢指针）」：每次走 1 步
• 「兔子（快指针）」：每次走 2 步

如果跑道是直的（无环），兔子先到终点。
如果跑道是环形的（有环），兔子在直线段可能领先，但「一旦进入环，兔子相对乌龟的速度是 1 步/次」，意味着每跑一次，两者的距离就缩短 1。因为环的长度是有限的，距离迟早会缩到 0——也就是相遇。

「结论：」 相遇 ⇔ 有环。无环 ⇔ 快指针先撞到 null。

🖼️ 图解全过程（手把手走一遍）

以链表3 → 2 → 0 → -4 → (回到 2) 为例：

🧠 「记住这个本质」：进入环后，快指针相对于慢指针每次只靠近 1 步。就像钟表上的分针追时针，速度差固定，必然重合。

💻 代码实现（Python + Java，附带空指针防坑）

Python 版（最简写法）

class Solution:    def hasCycle(self, head: Optional[ListNode]) -> bool:        slow = head        fast = head        # 只要 fast 能走两步，就继续走        while fast and fast.next:            slow = slow.next        # 慢走 1            fast = fast.next.next   # 快走 2            if slow == fast:                return True        return False

Java 版

public class Solution {    public boolean hasCycle(ListNode head) {        ListNode slow = head;        ListNode fast = head;        while (fast != null && fast.next != null) {            slow = slow.next;            fast = fast.next.next;            if (slow == fast) return true;        }        return false;    }}

⚠️ 「致命坑（必看）」：循环条件必须写成 fast and fast.next（Python）或 fast != null && fast.next != null（Java）。

如果只写 fast，当 fast.next 为 null 时，执行 fast.next.next 会直接抛出空指针异常。

「这是面试手写代码时最常犯的错误，没有之一。」

⏱️ 复杂度分析（面试必问）

• 「时间：O(n)」
  无环时，快指针走 n/2 步到末尾；有环时，慢指针最多走完环长 + 环外长度，整体 O(n)。
• 「空间：O(1)」
  只用了两个指针变量，这是Floyd算法碾压哈希表法的核心优势。

🚀 举一反三：4 道高频变种题，一套框架通吃

💬 面试追问模拟（提前准备，惊艳全场）

「Q1：为什么快指针每次走 2 步，慢指针走 1 步？走 3 步行不行？」

走3步存在“跨过”慢指针的风险。因为快慢相对速度 = 2，如果环长为偶数且初始距离为奇数，快指针会永远跳过慢指针，导致死循环（或极晚才相遇）。

「而步长2和1的相对速度 = 1」，每轮距离减 1，必然经历距离 = 0的瞬间，数学上保证相遇。

「Q2：相遇后，如何找到环的入口？（LC 142 核心）」

这是 Floyd 算法的第二阶段：

「Q3：如果链表很长（比如 10^6 节点），快慢指针会不会因为频繁跳转而性能变差？」

不会。时间复杂度依然是严格 O(n)，且因为空间 O(1)，在大数据量下反而比哈希表法更优（哈希表在碰撞时性能退化，且占用大量内存）。

🧩 实战小技巧（刷题党必备）

• 「口诀」：快二慢一，有环必遇；快空无环，慢中求偶。
• 「模板」：凡是链表中有“循环/重复/周期性”特征，优先考虑快慢指针。
• 「边界」：空链表（head=None）直接返回 False；单节点无环也 False。

📈 实际应用场景（不止是刷题）

• 「操作系统死锁检测」：资源分配图中检测循环等待。
• 「DNS 解析器」：检测域名 CNAME 记录是否存在无限重定向环。
• 「包管理依赖解析」：检测 Maven/npm 依赖图中是否存在循环依赖。
• 「伪随机数发生器」：检测随机序列是否进入短周期（Floyd 算法的原始应用）。

🎁 今日思考题（评论区见）

假设我们找到环的入口后，想计算「环的长度」，应该怎么做？
「提示」：在第一次相遇点冻结一个指针，另一个指针继续走并计数，直到再次相遇。
你能用 O(1) 空间写出伪代码吗？欢迎评论区贴出你的思路 🧠