企业官网建设流程全解析

环形链表 II 这道题，讲的是给定一个链表，让你找出环的入口节点。如果不要求额外空间，用哈希表一分钟就写完了；一旦要求空间 O(1)，就得掏出快慢指针这套经典解法。这篇文章会从题目拆解、Floyd 判圈算法的数学推导、三种语言实现细节、常见边界情况到扩展题型，完整过一遍。不管是刚接触链表的新手，还是准备面试想系统刷题的老手，这一篇应该都能让你把这道题彻底吃透。

1. 题目到底在问什么

1.1 题干要点拆解

原题的意思是：给你一个链表的头节点 head，链表中可能存在环。所谓环，就是链表的某个节点的 next 指针指向了它前面已经出现过的节点，导致遍历链表永远走不到尽头。题目要求你返回“环的入口节点”，也就是这个环开始的那个节点。如果链表无环，返回 null。

这里最容易混淆的是：不是让你判断“有没有环”，而是让你找到“环的入口在哪里”。判断有没有环只需要检测快慢指针是否相遇，那个题是第 141 题；而第 142 题是在确认有环的基础上，再多走一步，精确定位环的起始点。换句话说，141 题考的是“会相遇吗”，142 题考的是“在哪里相遇”。

光看题目表述，很多人第一反应是：我用哈希表记录每个经过的节点，一旦遇到一个已经在哈希表里的节点，它就是环的入口，因为它是第一次重新回到的节点。这个思路完全正确，也最容易理解。但题目通常有个更高的要求：能否只使用 O(1) 的额外空间来解？这个要求卡住了不少人，也是这道题真正想考察的算法思维。

1.2 和“判断是否有环”那题的区别

第 141 题只要返回布尔值，告诉你链表里有没有环。实现方案就是用快慢指针：慢指针一次走一步，快指针一次走两步，如果链表有环，快指针最终会“追上”慢指针；如果无环，快指针会先走到空节点。

第 142 题在此基础上升级了。确认有环之后，你还得返回环的起始节点。很多人以为“相遇的节点就是环的入口”，这是最大的误区。快慢指针第一次相遇的节点，只是环里的某个随机位置，并不一定是环的入口。只有当链表头到环入口的距离恰好等于环长度一半的倍数时，相遇点才会恰好在入口，这是特例，不是通法。

所以 142 题的关键，是在快慢指针相遇之后，再推导出一个恒等式，用一次“让慢指针从 head 重新出发，快指针从相遇点继续前进”的过程，最终找到入口。这一步是纯数学推导，理解了它，整道题就不再是背代码，而是能现场推导出来的真本事。

1.3 输入输出边界

这类题在在线评测平台上，链表结构已经定好的，通常是：

struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} };

需要注意几个边界输入：

• head 为 null，也就是空链表，直接返回 null。
• head.next 为 null，也就是只有一个节点，它不可能形成环，返回 null。
• 整个链表只有一个节点且自环，即 head.next == head，那么环入口就是 head 自己。
• 链表可能很长，入口可能在很靠前的位置，也可能就是第一个节点。

这些边界看起来简单，但代码里如果少写一个空指针判断，运行时就直接崩。后面章节我会专门列出来。

2. 解题前先想清楚的两条路

2.1 用哈希表记录 visited：最简单最稳定

先讲最直接的方法。用一个哈希集合保存已经访问过的节点，然后从 head 开始遍历。每走到一个节点，先检查这个节点是否已经存在集合里：如果存在，说明这是一个“回头路”，这个节点就是环的入口；如果不存在，就把它加入集合，继续走。

def detectCycle(head): seen = set() cur = head while cur: if cur in seen: return cur seen.add(cur) cur = cur.next return None

这个方案的时间复杂度是 O(n)，空间复杂度也是 O(n)。当 n 很大时，额外内存占用会比较明显。而且哈希表的开销也不小，尤其是链表节点多、node 对象又大的时候，set 里的内存增长很快。

但哈希表解法有一个不容忽视的优点：它不依赖任何数学推导，逻辑极其直观。面试中如果考官允许用额外空间，或者你一时想不起来快慢指针的推导，先答出哈希表解法再逐步优化，反而显得思路清晰。我见过不少候选人一上来就写快慢指针，但代码写错了；反而不如先给 O(n) 空间解法，再分析如何优化成 O(1)。

2.2 用快慢指针找入口：常数空间的经典做法

快慢指针的思路分两个阶段。

第一阶段是判环：slow 从 head 出发，每次走一步；fast 也从 head 出发，每次走两步。如果链表有环，那么 fast 必然比 slow 多走一些路程，最终会在环内某一点追上 slow，这就是第一次相遇。如果无环，fast 会先遇到 null，直接结束。

第二阶段是找入口：在第一次相遇的点，让一个指针从 head 重新出发，每次都走一步；另一个指针继续从相遇点出发，也每次走一步。两者再次相遇的位置，就是环的入口。

第二阶段为什么能保证相遇在入口？这是 Floyd 判圈算法（也叫托ortoise and hare 算法）的核心，后面的数学推导部分会详细展开。但先记住结论：相遇点“绕回入口的距离”，等于链表头到入口的距离。相当于两个等速指针一个从起点走，一个从相遇点走，最终会在入口碰头。

这个算法的总时间仍然是 O(n)，空间 O(1)。因为两个指针最多走常数圈，不会重复遍历太多遍。

2.3 为什么不是“第一次相遇的节点就是环节点”

我见过很多人第一次学到这里会很困惑。明明快慢指针都相遇了，为什么不直接返回这个节点？

举一个具体例子你就明白了。假设链表头到环入口距离是 7，环长度是 4。slow 走一步，fast 走两步。当 slow 走到入口时，它走了 7 步；fast 走了 14 步，也就是绕完 7/4 = 1 圈多 2 步？其实这里 fast 已经入环走了 7 步，换算成环内位置是距入口 3。继续走下去，slow 入环，fast 继续追，最终相遇点在环内某个位置。如果环长度不是 7 的因子之类的话，相遇点基本不会是入口。

所以“第一次相遇点”只是一次追及过程的自然结果，跟入口位置没有直接关系。要想得到入口，必须再做一次数学推导。这也是这道题区分“会背模板”和“真正理解算法”的地方。

3. Floyd 判圈算法的数学内幕

3.1 两阶段的本质：判环与找入口

Floyd 判圈算法对环的检测思路，本质上和“两人绕操场跑步，速度快的人追上了速度慢的人”是一回事。没有环的链表就是一条直线跑道，速度快的先跑到终点；有环的链表就是环形跑道，速度快的总会在某一圈套圈追上速度慢的人。

而找入口这个阶段，利用了“长度相等”的性质。把链表头到入口的距离记为 a，入口到第一次相遇点的距离记为 b，第一次相遇点继续走回入口的距离记为 c，环长度就是 b + c。利用 fast 走过的距离是 slow 的两倍，可以推出 a 与 c 的关系，进而设计出从 head 和相遇点同时走一步的解法。

这部分公式很多人见过，但未必能完全理解每个符号的意义。下一节我会把每一步拆开，用文字替代冗长公式来推一遍。

3.2 相遇位置推导：a、b、c 的含义

先定义三个关键变量，假设链表有环：

• a：从链表头到环入口的节点数，也可以理解成直线段长度。
• b：从环入口出发，沿着 next 方向走到第一次相遇点所经过的节点数。
• c：从第一次相遇点继续沿着 next 方向走，回到环入口所经过的节点数。

那么整个环的长度 L = b + c。

现在开始让 slow 和 fast 从 head 同时出发。slow 速度为 1，fast 速度为 2。当两者第一次相遇时，假设 slow 一共走了 s 步，fast 走了 2s 步。slow 走到相遇点的路程是 a + b，因为 slow 从链表头出发，走过直线段 a，进入环后再走 b 就到达相遇点。fast 走到相遇点的路程是 a + b + kL，其中 k 是 fast 在环内多绕的完整圈数，它可能在追上 slow 之前绕了好几圈，这是个未知的正整数（至少为 1）。

因为 fast 的路程是 slow 的两倍，所以有：

2 * (a + b) = a + b + kL

化简得：

a + b = kL

也就是 a + b 恰好等于环长度的整数倍。移项后得到：

a = kL - b

而 kL - b 又可以写成 (k-1)L + (L - b)，因为 L = b + c，所以 L - b = c，因此：

a = (k-1)L + c

这个式子说明：从链表头走到环入口的距离 a，等于“从相遇点继续往前走 c 步回到入口，然后再绕 (k-1) 圈”的距离。进一步简化就是：从相遇点走 c 步回到环入口，和从链表头走 a 步到环入口，两条路走完最终都到同一个点。

3.3 关键恒等式：从相遇点走到入口 = 从头走到入口

上面的恒等式 a = (k-1)L + c 是整套解法的发动机。

你可以想象：有两个人站在两个地方，一个人站在链表头，另一个人站在第一次相遇点。两个人以完全相同的速度往前走，每次都走一步。链表头的那个人要走 a 步才能到环入口，而相遇点的那个人要走 c 步就能到环入口。如果 a 恰好等于 c，那没问题；但一般情况下 a 不等于 c。不过，定理说的是，相遇点的人如果走 a 步，会走到哪里？

相遇点走 c 步到达入口，再走 (k-1)L 步也就是绕回去又回到入口，所以从相遇点走 a 步，也正好到达环入口。这就意味着，只要让两个指针以同样的速度向前走，一个从链表头出发，一个从相遇点出发，他们必然会在环入口相遇。

这就是第二阶段算法的依据：slow 重新指向 head，fast 保持在相遇点，两者每次走一步，直到 slow == fast，这个节点就是环的入口。

这个推导最妙的地方在于，我们根本不需要知道 k 是多少，也不需要知道 a、b、c 的具体数值，只需要知道相等的结论就能写代码。这也是算法笔记里常说的“数学一塌糊涂但代码两行”的原因：推导复杂，实现极其简练。

3.4 快指针为什么走两步，不走三步

一个自然的问题是：为什么 fast 每次走两步，而不是三步、四步？走三步不也能追到 slow 吗？

答案是：走三步在“判环”阶段确实也能追上，也一定能追上，但在环很小的情况下，快指针可能连续跨过慢指针所在的节点，导致“没有检测到相遇”吗？这里需要认真理一下，因为这里有个经典误会。

在链表节点构成的离散世界里，fast 如果一次走 3 步，它会从某个节点直接跳到下三个节点。而 slow 只走了 1 步。如果下一时刻 fast 的落点正好等于 slow 的落点，那能相遇；但如果 fast 从 slow 头上“跳过去”了，两者是不是就错过了？

实际上，在环内，fast 相对 slow 的速度是 2 步/时间单位（如果 fast 走 3，slow 走 1，相对速度是 2），相对速度为 2 意味着 fast 每单位时间靠近 slow 两步。由于环长有限，最终注定会落到同一点。即使 fast 曾经从 slow 头上跳过去，因为相对速度恒定为 2，它会在后续追上。所以走 3 步理论上也能实现判环。

但为什么标准解法都用两步？关键是后续找入口的推导。如果 fast 走 3 步，第一次相遇时，fast 走过的距离是 slow 的 3 倍，推导出的公式就不再是 a = (k-1)L + c 这么简洁，而是会多出一个和步长相关的余数条件。不同的步长会得到不同的“相遇点重新出发”策略，推导起来复杂，而且容易出错。走 2 步就是最经典、推导最简洁、实现也最安全的选择。

另外，从实际效率来说，fast 走 2 步已经能保证在慢指针走完一个环的长度前追上，效率已经很高，继续加步长没有收益。

4. 三种语言的实现与细节

4.1 Python 实现：写起来最舒服

class ListNode: def __init__(self, x): self.val = x self.next = None def detectCycle(head): if not head or not head.next: return None slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: start = head while start is not slow: start = start.next slow = slow.next return start return None

Python 版本注意三件事。第一，判断初始空链表时用 not head 或 not head.next，不要用 head == None 这种写法，虽然也能运行但不够 Pythonic。第二，判断两个节点是否相同，用 is 而不是 ==。链表节点对象是引用类型，is 比较的是内存地址，这和我们找“同一个节点”的目标完全一致；而 == 在大多数自定义实现下会走对象默认比较，也可能比较值，容易出岔子。第三，while 条件 fast and fast.next，如果没有 fast.next 的检查，在链表长度为偶数、无环的情况下，fast.next 会变成 None，下一轮 fast.next.next 就会抛异常。

4.2 Java 实现：空指针是最大的敌人

public class Solution { public ListNode detectCycle(ListNode head) { if (head == null || head.next == null) { return null; } ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { ListNode start = head; while (start != slow) { start = start.next; slow = slow.next; } return start; } } return null; } }

Java 版本最容易翻车的点就是 fast.next.next。while 循环的终止条件已经写了 fast != null && fast.next != null，这意味着在循环体里访问 fast.next.next 是安全的。因为 fast.next 不为空，fast.next.next 有可能是 null，但访问是允许的，只是下一轮循环会因 fast == null 或 fast.next == null 退出，不会出问题。

另一个很多初学者犯的错误，是在结束判环循环后，没有写 return null。Java 编译会直接报错：缺少返回值。因为编译器能看出来 while 有可能一次都不执行，或者正常退出，所以必须在方法末尾补上 return null。

4.3 C++ 实现：指针操作的快感

class Solution { public: ListNode *detectCycle(ListNode *head) { if (head == nullptr || head->next == nullptr) { return nullptr; } ListNode *slow = head; ListNode *fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if (slow == fast) { ListNode *start = head; while (start != slow) { start = start->next; slow = slow->next; } return start; } } return nullptr; } };

C++ 版本和 Java 版本几乎是同构的，但有一个很小的区别：有人喜欢把 head == nullptr 和 head->next == nullptr 合并成 if (!head || !head->next)。这个写法能用，但可读性一般，尤其对刚转 C++ 的人，建议写成显式 nullptr 比较。另外，在 C++ 里，节点对象是手动 new 出来的，算法本身不负责 delete，所以无需考虑内存释放问题，只需要保证遍历时不访问空指针。

4.4 容易被忽略的空指针与边界

刚才三个版本里，头部的边界检查都是同一个套路：head 为空，或者 head.next 为空，直接返回 null。为什么 head.next 为空也要直接返回？因为只有一个节点的链表不可能有环（除非自环，但自环时 head.next == head，这在 head.next 不为空的前提下是成立的，所以需要区分）。实际上，head.next == null 说明只有一个节点，无环；head.next == head 说明自环，这属于 head.next 不为 null 的情况，会进入主循环，并由后续逻辑处理。

还有一个容易被忽略的边界：链表无环时，主循环正常退出，返回 null。有些初学者会在循环外面随手写 return head，这显然是错的。

我在实际刷题时，有一个小习惯：写完代码后，先手动模拟空链表、单节点无环、单节点自环、双节点无环、双节点自环、长链表有环入口在第一个节点等几个极端样例。这几个样例跑通了，基本就不会有低级错误。

5. 现场实战：几个典型样例走一遍

5.1 样例1：有环，入口在中间

假设链表是这样的：

3 -> 2 -> 0 -> -4 ^ | |_________|

也就是 -4 的 next 指向 2，环入口是节点 2。链表头到入口 a = 1，环由 2、0、-4 三个节点组成，环长度 L = 3。

慢指针和快指针都从 3 出发。slow 走一步到 2，fast 走两步到 0。slow 到 0，fast 到 -4。slow 到 -4，fast 走两步：先到 2，再到 0。此时 slow 在 -4，fast 在 0，还没相遇。slow 到 2，fast 到 -4，相遇点在 -4。

此时执行第二阶段：start 从 head 出发，slow 继续从相遇点 -4 出发，两个都每次走一步。start 下一步到 2，slow 下一步到 2，相遇，返回 2。正好是环入口。如果还有疑虑，可以继续推：start 从 head 到 entry 走了 a=1 步，slow 从相遇点走 c 步（c 是相遇点到入口，这里 c = -4 -> 2，正好是 1 步），所以同时到达。

这个例子的 a 和 c 恰好相等，可能不太有说服力。换个数据。

5.2 样例2：整个链表就是环

另一种情况：链表头就是环入口。比如：

1 -> 2 -> 3 -> 1

a = 0，环长度 L = 3。

slow 和 fast 从 1 出发。slow 到 2，fast 到 3。slow 到 3，fast 到 2。slow 到 1，fast 到 1，第一次相遇在 1。第二阶段，start 从 head（也就是 1）出发，slow 从相遇点（也是 1）出发，两者一上来就相等，直接返回 1。环入口就是 head 本身，符合预期。

如果整个链表首尾相接，第二阶段的 while 循环一次都不用执行，函数直接返回 head。这种边界情况恰恰是很多代码容易写错的地方，因为有人会把 start 初始化为 head.next，或者误以为必须进入循环才能找到入口。

5.3 样例3：自环

自环是最好玩的边界：只有一个节点，并且这个节点的 next 指向自己。head.next == head，所以环入口就是 head。

进入主循环，slow 和 fast 都从 head 出发。slow = slow.next 得到 head，fast = fast.next.next 也得到 head，第一次相遇就是 head。第二阶段 start = head，slow = head，直接相遇，返回 head。整个过程没有一步多余。

如果前面头部检查写成了 if (head == null || head.next == null) return null，自环反而没被拦住，因为 head.next 是 head，不是 null。很好，这个检查逻辑是安全的。

6. 常见问题与踩坑记录

6.1 为什么 fast 初始指向 head 而不是 head.next

网上很多版本的代码会把 fast 初始化为 head.next，slow 初始化为 head，这样做的原因是让循环一开始就不同步，方便在 while 里判断。这种写法也能通过题目，但第二阶段找入口时，相遇点的含义会有细微变化，推导起来不如统一初始化为 head 来得干净。

统一把 slow 和 fast 都初始化为 head，代码更对称，语义也更清晰。在进入循环前，需要确保 head 不为空，且 head.next 不为空，否则 fast.next.next 会出问题。统一从 head 出发还有一个好处：如果链表无环，slow 和 fast 的移动逻辑对称，不容易把自己绕晕。我的建议是始终用同一套初始状态，省得在不同写法之间来回切换。

6.2 死循环与超时

有些人在判环阶段没有写 while 条件的空指针检查，或者把循环条件写错，导致链表无环时 fast 走到 null 还继续访问 fast.next，直接抛异常。更隐蔽的问题是：如果 fast 的移动步长随意设置，比如一次走 3 步，在环很长时确实也能相遇，但环长和步长之间的数学关系不清晰，可能让循环次数增加，甚至在某些极端构造下变得极慢。

标准解法不会死循环，因为只要存在环，快慢指针必然相遇；不存在环，循环会自然退出。但如果你改了步长或者初始位置，就需要重新推导。我记得有一次为了测试，用了 fast 走一步、slow 走一步的等速指针，结果在有环的链表里两个指针永远不相遇，死循环，最后超时。那次经历让我彻底明白：等速指针只会保持相对静止，判不了环。

6.3 返回值到底返回哪个节点

第二阶段里有两个指针，一个是 start 从 head 出发，另一个是 slow 从相遇点出发。当它们相等时，返回哪一个都可以，因为此时它们指向同一个节点。但要注意，第二阶段里 slow 不能改名为 faster 或者其他容易混淆的名字，否则代码读起来很别扭。

还有，有人会把 start 写成 third，或者 fast2，然后想着“fast2 是从 fast 那边来的，应该和 slow 保持一致”。只要逻辑清楚，名字随意。我见过一份代码里，第二阶段用的是另一个指针 q，q 从相遇点出发，p 从 head 出发，最后返回 p。这样也正确，只是可读性差一些。关键是理解：第二阶段的两个指针，速度都是 1，起点分别是 head 和第一次相遇点。

6.4 快指针步长选 2 的替代方案

如果非要用快指针步长 3，判环阶段一样可行。你还得额外考虑：如果环长和步长之间满足某种关系，第一次相遇点对应的 c 值和 a 值的关系会变化，第二阶段就不能再用“两指针各走一步”的简单办法，可能需要走更多步才能找到入口。这会让代码复杂度上升，而且面试时推导这个公式的时间成本太高。

所以我的结论是：标准方案就是最快、最稳、最好理解的方案。步骤变来变去反而容易出错。做题不是为了炫技，而是为了在最短时间内给出正确且能解释清楚的方案。

7. 从这一题延伸出去

7.1 环的长度怎么求

既然已经能定位环的入口，求环的长度就很简单了。找到环入口之后，在入口处停一个指针，然后每次走一步并计数，直到重新回到环入口，计数结果就是环的长度。这个操作的时间复杂度是 O(L)，其中 L 是环的节点数。

还有另一个方法：在第一次相遇点处继续走，每走一步计数，再次回到相遇点时计数结果也是环长。因为第一次相遇点本来就在环内，所以从这个点出发绕一圈必然回到自身。这个方法和从入口计数本质一样，但代码里可以省一次第二阶段调用，直接得到结果。如果你想在原来代码的基础上改，我建议用第二种，改动最小。

def cycle_length(head): slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: cur = slow length = 1 cur = cur.next while cur is not slow: length += 1 cur = cur.next return length return 0

7.2 寻找重复数的隐藏解法

有一个经典题目，给你一个长度为 n+1 的数组，里面的数字都在 1 到 n 范围内，假设只有一个重复的数字，让你找出来。要求不能修改数组，也只能用常数空间。

正常思路是二分或者位运算，但更巧妙的是把它转化成链表问题：把数组下标看成节点，下标 i 对应的值 nums[i] 看成 next 指针。因为存在重复值，必然有两个下标指向同一个值，而这个值就是环入口。利用这道题学到的快慢指针找入口方法，可以直接求出重复数。我第一次看到这个转化时确实拍案叫绝，因为链表的快慢指针算法居然能跑到数组里。

这其实说明了：快慢指针找环的本质不是链表特有的算法，而是“函数迭代轨迹”上的判圈算法。只要你能把数据组织成 f(x) 的迭代形式，就可以用。

7.3 链表交点问题与环的联系

另一个常见题型是求两个链表的交点。常规做法是用两个指针分别遍历两个链表，如果相交就返回交点。这个题目还有一个思路，是把其中一个链表的尾部接到另一个链表的头部，构造出一个环，然后用环形链表的入口算法来找交点。虽然实际写代码时直接用双指针更简单，但从原理上看，环形链表的思路能加深对问题的理解。

用这种方法思考，你会发现：fast 和 slow 在环里相遇的过程，和两个链表指针交错的过程有相似之处。本质上都是“走不同的路，最终殊途同归”。

7.4 关于空间复杂度优化的心得

这道题最核心的收获，不是背下来一个算法，而是理解“空间换时间”和“时间换空间”的权衡。哈希表解法空间复杂度 O(n)，但代码直观，几乎不用解释；快慢指针解法空间复杂度 O(1)，但需要数学推导。很多人在面试时会不自觉偏向哈希表，因为安全、不容易出错。但如果题目明确要求空间 O(1)，就必须掌握快慢指针。

我的建议是，两种解法都要练会，并且能在一分钟内从哈希表解法切换到快慢指针解法。因为面试官很喜欢先让你用哈希表做，然后问“能不能不用额外空间”。如果你能当场推演 Floyd 算法，而不是磕磕绊绊背代码，印象分会高出不少。

8. 这段推导值得反复咀嚼

这道题看起来只有短短几行代码，背后却藏了一整套数学推导。我最早学的时候，也是先背了代码，后来某一次在纸上画链表演示时，才真正理解 a = (k-1)L + c 的意思。从那以后，哪怕几个月不写这段代码，我也能在几分钟内重新推回来。这比记忆代码要可靠得多。

如果让我给一个学习路径的建议，那就是先画图。拿纸笔，随便画一个有环链表，标出 a、b、c，然后手动模拟 slow 和 fast 的移动过程。多模拟几轮之后，你会发现“快指针多走的路程 = 慢指针路程的两倍”这句话是整道题的钥匙。等这个式子刻在脑子里，第二阶段的两个指针为什么要从不同起点出发，就再也不会忘记了。

最后再分享一个实际排查中的小技巧：写跑题主循环后，先在脑子模拟一个无环链表的例子，确保循环能退出；再模拟一个有环链表，确保第二阶段不会死循环。这两个都是极简单但极有效的自测方式。毕竟这种链表题，debug 起来不像数组题那么直观，日志都不容易打，逻辑正确性只能在写代码时确保。