企业官网建设流程全解析

如果你也在刷 LeetCode Hot100，到了第 23 题，大概率会碰上一道让人眉头一皱的链表题——142. 环形链表 II。这道题很多人在“判断链表有无环”的阶段还能轻松写出来，但一要求“返回入环的第一个节点”，就开始卡壳。Hot100 把这个题放在链表专题里，不是为了让你背一个双指针模板，而是想逼你理解“相遇位置”和“环入口”之间的数学关系。这篇文章我会从题意、暴力解法、双指针推导、边界条件到刷题心法全部过一遍，希望你刷完之后不是记住代码，而是能推出来。

1. 题目到底在问什么

1.1 题目描述与输入输出

原题给的是一个单链表的头节点 head，链表中可能存在环，也可能没有环。要求返回链表开始入环的第一个节点，也就是环的入口节点；如果链表无环，返回 null。注意题目要求不修改链表结构。

很多同学第一次看会以为这题只是“判断有没有环”，但实际它比 141. 环形链表多了一步：不仅要得出“有环”的结论，还要精确定位环的起点。输入是一个链表的头节点，输出是环入口节点本身，而不是下标或布尔值。在代码里，这个“节点本身”就是一个对象引用，所以最后返回的必须是链表中实际存在的节点。

举个例子，1 -> 2 -> 3 -> 4 -> 2，这个链表里 2 被重复访问，那么入环节点就是 2。如果链表是 1 -> 2 -> 3 -> null，无环，结果就是 null。如果头节点自己指向自己，入环节点就是 head。这些边界场景在后面测试时一个都跑不掉。

1.2 链表中“环”的两种形态

链表的环不像图中那种任意两个节点相连的复杂环，它只可能是因为某个节点的 next 指针指向了之前的节点，导致单向链路变成了一个“圆圈尾巴”。这分成两种常见形态：

第一种是“0 型环”，也就是整个链表首尾相接，比如 A -> B -> C -> A。此时没有真正的“链表终点”，所有节点都在环内，入环节点就是头节点 A。第二种是“6 型环”，前面有一段非环的“尾巴”，后面才进入环，比如 1 -> 2 -> 3 -> 4 -> 5 -> 3，此时入口是 3。绝大多数题目用例都是第二种，因为这样才能考察你如何区分“链外距离”和“环内距离”。

很多人在纸上画图时能看出来入口在哪，但一写代码就无从下手，关键在于你没有一个“记录访问过节点”的直觉。哈希表方案就是顺着这个直觉来的，但它并不是最优解；最优的双指针方案则完全绕开了额外空间。

1.3 为什么这题值得进入 Hot100

Hot100 里的题不一定是算法最难的，但一定是面试里最高频、最能体现思维深度的。环形链表 II 恰好覆盖了链表操作、快慢指针、数学推导、边界条件四个核心考点。面试官可以只问第一问“有没有环”，也可以追问第二问“入口在哪”，还可以继续追问“环的长度是多少”“如何求链外长度”，这些都是从这题延伸出来的。

更重要的是，这题能考察候选人是否真正理解双指针，而不是死背模板。因为很多人会写快慢指针相遇判断，但一旦要解释“为什么相遇后从头节点和相遇点同时走，最终会到入口”，就说不清楚了。能完整推导出来的人在系统设计、复杂逻辑拆解上的能力通常也更强，这就是 Hot100 把它放在前几十题里的原因。

2. 先讲能最快上手的哈希表写法

2.1 哈希表思路其实一句话

遍历链表，把每个访问过的节点存进 Set 里。如果某个节点已经存在，就说明这个节点是环的入口；如果遍历到了 null，说明无环。

为什么第一个重复节点一定是入口？因为环内节点从入口开始，走一整圈最后又回到入口；你第一次“第二次看到”某个节点时，必然是走完一圈后回到了起点。这个起点就是环入口。链外的节点不会重复，所以第一个重复节点只能是入口。

这种思路非常直觉，也最容易写对。它不需要任何数学推导，只需要一个 HashSet。时间复杂度 O(n)，空间复杂度 O(n)。对于 LeetCode 而言，这个解法能直接通过，所以很多同学就这么提交了。

public ListNode detectCycle(ListNode head) { Set<ListNode> seen = new HashSet<>(); while (head != null) { if (!seen.add(head)) { return head; } head = head.next; } return null; }

因为 HashSet 的 add 方法在元素已存在时会返回 false，所以这里用!seen.add(head)来判断重复非常简洁。如果你更喜欢显式写法，也可以先if (seen.contains(head)) return head;，再seen.add(head)，只是多一步查询。

2.2 为什么哈希表写法能轻松通过

这题的题目性质决定了哈希表是“顺理成章”的方案。你不需要考虑快慢指针的相遇条件，也不需要处理 fast.next 可能为空的烦恼，只要一直沿着 next 走，把路过的节点记下来就行。

对于链表长度为 n、环长度为 L 的情况，哈希表最多存放 n 个节点，内存开销可控。LeetCode 对这类题的空间限制通常不会卡出 O(n)，所以哈希表解法在通过率和可读性上都非常稳。特别适合刚接触这道题、对双指针还不太熟的同学先跑通逻辑。

但有一个细节要注意：题目要求返回“节点”，而不是“节点的值”。链表里可能有重复数值，但节点对象本身不同，所以 HashSet 里存的是节点引用。你在代码里不能只比较 val，否则遇到两个值相同的不同节点就会误判。

2.3 为什么面试官通常想让你再优化

哈希表写法虽然能过题，但面试时不一定是加分项。因为面试官问这题，十有八九会接着问“能不能只用 O(1) 空间解决”。这时候如果你只给出哈希表方案，相当于选择了一个容易想到但不够优雅的解法。

O(n) 的额外空间意味着随着链表增长，内存线性上升。如果链表特别长，比如上百万节点，哈希表的扩容、hash 计算、对象引用存储都会有额外开销。在嵌入式、底层系统这类对内存敏感的场景里，这种方案显然不够友好。

更重要的是，Floyd 双指针法是链表问题里的经典思想，它不仅能解决这道题，还能推导出一系列变体问题。面试官希望你展示的是“从暴力到最优”的演进过程，而不是停在“能过就行”的层次。所以我一直建议：哈希表用来保底，双指针才是必须掌握的核心。

3. Floyd 双指针法的完整推导

3.1 快慢指针为什么必然相遇

Floyd 判圈算法大家应该不陌生：慢指针 slow 每次走 1 步，快指针 fast 每次走 2 步，如果链表有环，两个指针最终一定在环内相遇；如果无环，fast 会先碰到 null。

这里有一个关键问题：为什么一定会相遇，而不是 fast 每次都跳过 slow？你可以想象两个人在环形操场上跑步，fast 每秒跑 2 米，slow 每秒跑 1 米。一开始 fast 在前面，slow 在后面，但 fast 比 slow 快 1 米/秒（相对速度是 1），所以每过一秒，fast 离 slow 的距离就缩短 1 米。只要操场是环形的，fast 迟早会追上 slow，而且不会出现“刚好跨过去”的情况。

注意，fast 进入环的时候，slow 可能还没进环，也可能已经走了一段。但只要两个指针都在环内，fast 相对 slow 每步逼近 1 个节点，最多走完整圈环长度就能相遇。即使 fast 从正后方追赶，也不会漏掉 slow，因为相对速度是 1，每一步都会让距离减一，连续变化没有跳跃。

3.2 相遇之后如何定位入口，公式推导

这一步是整道题的灵魂。假设链表头节点到环入口的距离为 a，环入口到两指针相遇点的距离为 b，相遇点继续走回环入口的距离为 c。那么环的周长 L = b + c。

两个指针从 head 同时出发，slow 每步走 1，fast 每步走 2。假设 fast 已经在环内跑了 n 圈后才追上 slow（n 是正整数，可能是 1、2、3……）。相遇时：

• slow 走过的总距离：a + b
• fast 走过的总距离：a + b + nL

因为 fast 的速度是 slow 的两倍，所以 fast 走过的距离等于 2 倍的 slow 距离：

2(a + b) = a + b + nL

化简得到：

a + b = nL

也就是说，从链表头到相遇点的距离，正好等于环周长的 n 倍。接着移项：

a = nL - b

因为 L = b + c，所以：

a = n(b + c) - b = (n - 1)L + c

这个式子太重要了。它说明：从链表头到环入口的距离 a，等于“在环内多走 n-1 圈之后，再从相遇点走回到环入口的距离 c”。

所以方法就是：当 slow 和 fast 相遇时，另起一个指针 ptr 指向 head，然后让 ptr 和 slow 以相同速度一步一步往前走。ptr 从 head 走到环入口，需要 a 步；slow 从相遇点出发，走 c 步回到环入口，再走若干整圈，最终也会在环入口与 ptr 相遇。两者相遇的位置就是入环节点。

3.3 用生活化例子理解 a=(n-1)L+c

这个公式很容易背错，所以我想用一个直观例子帮你记住。

想象一条从家到操场的路，家到操场入口的距离是 a。你从家出发，先走一段路到操场入口，然后进入环形跑道。你在跑道上跑了一会儿，和一个朋友在某点相遇。你们相遇后，你继续往前跑，只需要再跑一段距离 c 就能回到操场入口；如果跑累了，你可以选择多跑几圈再停下来，反正只要经过入口，就算到达目标。

等式的右边(n-1)L + c说白了就是：从相遇点出发，先跑完剩下的 c 到入口，然后你可能额外绕了 n-1 圈。但不管绕多少圈，最终经过的点一定是入口。于是你让另一个人从家出发，你从相遇点出发，两人同速，你们最终会在操场入口碰面。

我每次刷到这题都会把这个场景在脑子里过一遍，比硬记公式靠谱得多。你还可以画一个简单的示意图：一条直线接一个圆，标出 a、b、c、L，然后反复推导几遍，印象会非常深。

3.4 边界情况验证

公式推导完之后，一定要验证几个边界情况，否则写出的代码容易在特殊用例上出错。

如果链表无环，快指针会先遇到 null，此时直接返回 null，不需要进入相遇后的流程。如果头节点为 null，或者只有一个节点且 next 为 null，也直接返回 null。

如果入环节点就是头节点，也就是 a = 0，那么 slow 和 fast 相遇后，从 head 出发的 ptr 一开始就在入口。此时 ptr 和 slow 不一定相等，所以 while 循环还是会走；但根据公式，slow 最终会在入口追上 ptr。代码里不能用“如果 ptr == head 就直接返回 head”来优化，因为 head 指针指向的是同一个对象，head 本身就是入口，这个判断没有意义，直接走循环直到相等即可。

还有一个容易出现幻觉的地方：fast 指针的初始化。有些写法把 fast 初始化为 head.next，这样会让相遇点和公式推导中的定义不一致。个人建议老老实实让 slow 和 fast 都从 head 开始，代码更清晰，公式也对得上。

4. 代码落地：三种语言实现与易错点排查

4.1 Java 实现与注释

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 ptr = head; while (ptr != slow) { ptr = ptr.next; slow = slow.next; } return ptr; } } return null; }

这段代码的关键点有三个。第一个是if (head == null || head.next == null)，先把无环或空链表直接挡掉，避免后面fast.next.next空指针异常。第二个是循环条件fast != null && fast.next != null，因为 fast 每次走两步，如果不检查 fast.next，可能会出现空指针。第三个是相遇后另起指针，让 ptr 和 slow 同速走，这里不需要再移动 fast。

很多人会疑惑为什么相遇后不再管 fast，直接操作 slow 和 ptr 就行。因为 fast 只是“探路者”，它的任务已经完成，后面的定位只需要两个同速指针相向而行的数学性质。

4.2 Python 与 C++ 实现要点

Python 写法与 Java 几乎一样，但要注意is和==的区别。链表节点是对象，判断两个节点是否同一个引用，应该用is；如果用==，需要节点类实现了__eq__，否则默认也是比较引用。力扣的 ListNode 没有实现自定义__eq__，所以is和==在这题里都可以，但习惯用is更安全。

def detectCycle(head: ListNode) -> ListNode: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: ptr = head while ptr is not slow: ptr = ptr.next slow = slow.next return ptr return None

C++ 主要注意指针判空，以及不要写成while (fast && fast->next)后漏掉 nullptr 判断。C++ 中节点指针比较直接用==，比较的是地址，天然符合题意。

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

4.3 空指针、自环、无环等边界用例

我刷题时吃过不少亏，这里把最容易翻车的几个场景列出来。

空链表示例：输入为 null，直接返回 null。这个很简单，但不少同学在写 while 循环前忘了判断，导致后续访问 head.next 直接异常。单节点无环：1 -> null，slow 和 fast 都从 head 出发，进入循环前需要判断 head.next 是否为空，代码里已经挡掉。如果漏掉这个判断，fast.next.next 会空指针。

无环长链：1 -> 2 -> 3 -> 4 -> 5 -> null，fast 会先走到 null，循环退出，返回 null。这里不会出现 slow 和 fast 相等的情况，因为无环时快指针永远在慢指针前面，不会有追赶相遇。

自环节点：1 -> 1。head 本身就是入口，slow 和 fast 初始都是 head。第一次循环时 slow 变成 head，fast 变成 head.next（还是 head），然后 fast.next.next 依旧是 head。slow 和 fast 刚好会在第二次或第三次比较时相等。相遇后 ptr 初始为 head，slow 也是入口，while (ptr != slow)不执行，直接返回 head，正确。

环很长且入口靠后的情况：例如入口离 head 有 100 个节点，环长度 1000，slow 和 fast 需要先走完链外距离，再在环内追赶。只要环存在，fast 一定能在有限步内追上 slow，因为进入环后相对速度是 1。代码不需要额外处理链外距离，公式已经保证了相遇之后 ptr 和 slow 会同步到达入口。

4.4 常见错误排查速查表

这里整理一个我在调试环形链表问题时经常对照的速查表，覆盖几种典型报错或错误输出的原因：

我在实际刷题中的习惯是：先写哈希表解法跑通，再用双指针解法重新推导一遍。如果双指针代码出错，我会把链表长度和环入口打印出来手动模拟几步，这样比盯着代码干想高效得多。

5. Hot100 刷题心法：环形链表这类题怎么想

5.1 把环形链表专题串起来

LeetCode 里和环形链表相关的题不少，141、142、287 都是同一套思想的不同变体。Hot100 里 142. 环形链表 II 属于最经典的“找入口”问题，刷透这一题之后，再看 287 寻找重复数会有一种“原来这也是一回事”的感觉，因为数组下标和值可以映射成链表节点，快慢指针一样能找到重复位置。

我自己刷 Hot100 的习惯是：不孤立地看题，而是把一个专题里的题放在一起对比。环形链表 I 练“有无环”，环形链表 II 练“找入口”，如果还想加深，可以自己问自己：怎么求环的长度？答案是相遇后让 slow 继续走，同时计数，直到再次碰到 fast 或回到相遇点，走的路程就是环长。这些变体都是从 142 的知识点长出来的。

5.2 识别同类题与算法套路

Hot100 里很多题看起来完全不同，底层套路可能是相通的。双指针类题目除了“快慢指针判环”，还有“左右指针逼近”“滑动窗口固定快慢步长”等变体。如果你能在做题时主动归类和总结，刷完 Hot100 后面对新题会从容很多。

比如遇到“找重复数”这类题，如果题目限制空间 O(1)，大概率就是想让你用链表判环的思维；如果遇到“最多能吃到多少香蕉”这种带单调性的问题，比如 LeetCode 875 爱吃香蕉的狒狒，本质上又是二分查找的套路。不要因为题号差得远就认为没关系，算法题的分门别类是刷题效率的关键。

5.3 面试时的表达顺序：从暴力到最优

如果你在面试中碰到这题，我建议按这个顺序表达：先确认题意，问清楚是否有环、是否可修改链表、返回节点还是下标；然后给出哈希表解法，并说一句“这是空间 O(n) 的解法，可以优化”；接着推导 Floyd 双指针法，把 a、b、c、L 的关系讲清楚，最后再写代码。

面试官一般不会因为你先提哈希表而扣分，扣分点是提完哈希表后不会优化。所以哪怕你第一反应是哈希表，也要主动展示你懂双指针。推导公式时可以边说边画，把“从 head 到入口的距离 = 从相遇点继续走到入口的距离，加上若干个整环”这句话讲明白，比直接把代码甩出来更有说服力。

5.4 一点个人刷题经验

这题我在 Hot100 里至少刷过三遍。第一遍只记住了代码，第二遍才开始逐行推导公式，第三遍才真正理解为什么相遇后要让一个新指针从 head 出发。每一次重刷都会有新理解，尤其是对快慢指针的“相对速度”这个概念。

如果你现在看到这题还觉得两个指针相遇很玄学，我建议你动手画一个 6 型链表，把 slow 和 fast 每一轮的位置都标出来，标三轮之后你就发现规律了。再回到公式推导，a=(n-1)L+c 就不再是死记的公式，而是你亲眼看到的事实。刷题这件事，慢就是快，把一道经典题彻底吃透，比囫囵吞枣十道题有用得多。