企业官网建设流程全解析

但凡刷过一段时间算法题的人，基本都会撞上“环形链表二”这道题。我第一次做它的时候，觉得既然前面已经有一道“环形链表一”把“有没有环”判断完了，这题无非是再跑一次快慢指针，把相遇节点返回去而已。结果真动起手来才发现，判断环只需要快慢指针一跑，找入口却要把距离关系算清楚。多少人卡在这一步并不是不会写代码，而是没弄明白：为什么两个指针已经相遇了，还不是环的入口？这篇文章就是围绕这个“为什么”展开的，新手可以看完整推导，面试前突击的人可以直接跳到代码和避坑清单。

1. 题目到底在说什么

1.1 从题目名称说起：什么是“环形链表二”

单链表的结构很简单：一个节点只存一个值和next指针，next指向下一个节点。正常情况下，最后一个节点的next指向null，链表就能走到头。但总有例外——如果某个节点的next没有指向null，而是指回了链表里更早的某个节点，链表的尾部就和前面接上了，形成一个环。环形链表二给一个头节点head，要求找到“环的入口”并返回这个节点；如果链表没有环，就返回null。

“二”这个字是和基础版对应的。基础版只问到底有没有环，返回布尔值就行；第二版非要问环从哪里开始。这个看似只多了一步，实际上多出来的正是核心难点：你要定位入口，而不是证明环的存在。很多在线判题环境在测试时会额外告诉你pos的值，表示尾指针指向的是链表中第几个节点。但真正写函数时，你手里只有一个head，其他信息一概没有。你要做的是在只有头节点的情况下，把这个入口找出来。这个限制很关键，意味着你不能先遍历一遍记住所有节点再回头找，因为那正是哈希表解法的空间代价。

1.2 输入输出与边界条件，先看清楚再动手

在写代码前，最好先把输入输出画清楚。函数签名大致是：

struct ListNode { int val; ListNode *next; }; ListNode *detectCycle(ListNode *head);

看这个签名就知道，链表节点是单链结构，也没有提供“环入口”这样的参数。你只能通过指针移动去判断。

我习惯先列边界条件，再写核心逻辑。因为链表题的崩溃往往不是出在复杂场景，而是最基本的场景没考虑：

不少人的解法在普通情况下完全正确，但在空链表或单节点时直接报空指针异常，这就是一开始没做边界检查。链表题有一种很典型的犯错方式：核心逻辑写对了，边界判断丢了。面试中这扣分比逻辑错误还冤。所以动手之前先立边界，后面写代码时会轻松很多。

2. 从最容易想到的解法入手：哈希表法

2.1 为什么第一反应是哈希表

假如你走进一座迷宫，想知道从哪里开始绕圈，最笨但最可靠的方法是什么？把走过的每一个路口都记下来。每走到一个新路口，先看一看笔记里有没有它——如果出现过，说明你已经绕回曾经来过的地方，这里就是循环的起点。

链表也一样。每个节点都有唯一的内存地址，这个地址天然可以做哈希。你不需要知道环的数学性质，只需要把见过的节点地址存进集合，一边走一边查。这种解法几乎是“条件反射”，任何人都能想到。

关键是它足够正确。只要链表有环，你沿着next走，一定会第二次踩到某个节点；这个节点就是环的入口。如果链表无环，走到底必然遇到null，集合里存的节点都不会重复，返回null即可。

2.2 哈希表解法的完整步骤与代码

直接用集合实现，Python代码非常简单：

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

代码逻辑只有四步：当前节点是否在seen里，在就返回；不在就加入；指针后移；遇到None就返回空。

使用集合时，有一个细节很多人不注意：链表节点的哈希值通常是基于对象身份计算的。Python的set会先调用对象的哈希函数，再判断相等。如果没有自定义__hash__和__eq__，默认就是按对象内存地址来的，完全符合题目要求。如果你在工程代码中自定义了节点类，务必小心重写__eq__后哈希函数是否还一致，否则set可能产生不期望的行为。这属于额外工程经验，但能在面试中展示边界意识。

用一个例子验证：链表是A->B->C->D->E->C，也就是从C开始绕圈。遍历过程：把A、B、C、D、E依次加入集合；继续走到C时，发现C已经在集合里，立刻返回C。这个C就是环入口。整个过程不需要任何数学推导，也不容易出错。

2.3 哈希表法的复杂度与短板

哈希表法的时间复杂度是O(n)，空间复杂度也是O(n)。在线判题系统通常不会为难这种解法，跑起来也不会超时。但如果面试官紧接着问“能不能把空间复杂度降到O(1)”，哈希表法就暴露短板了。

链表本身就靠next指针串起来，理论上你有办法用有限个指针完成判断和定位。额外开一个哈希表，相当于用内存换思路。这不算错，可对于追求简洁解法的人来说，不够漂亮。

另一个考虑是环境限制。如果链表节点被设计为不可哈希，或者题目要求不得使用额外存储空间，哈希表法就直接出局。所以它更适合作为“兜底方案”或“验证答案的方法”，真正要吃透这道题，还是得理解快慢指针。

3. 经典解法：快慢指针，我们到底在追什么

3.1 快慢指针判断环的核心思想

快慢指针的思路不复杂：两个指针slow和fast同时从head出发，slow每轮走一步，fast每轮走两步。如果链表无环，fast会先走到null；如果有环，fast最终会从后面追上slow。

这个追及过程可以类比操场跑步。两个人同向跑，一个人快，一个人慢，只要跑道是闭合的，总有一刻会追上。链表里的环就是闭合跑道；没有环，跑道就是一条直线，快的人会直接跑出边界。

有一个问题面试官经常追问：为什么快指针走2步，不是走1步，或者走3步？如果slow和fast都走1步，两者速度一样，一个永远无法追上另一个。走3步呢？每轮之间两者距离变化是2，快指针可能从慢指针上方“跳”过去，绕一圈后仍然错过，导致永远不相遇。走2步意味着每轮距离缩小1，是能够保证追上且不跳过的选择。这背后的道理比背结论重要得多。

需要注意的是，这个“从head同时出发”的设定很关键。有些人会写成slow=head，fast=head->next，这样判断有无环仍然可行，但fast比slow提前进入环，相遇点的含义就会变化，后面找入口的数学关系就不成立了。所以标准解法里，起点一致是前提。

3.2 从“相遇”到“入口”的距离公式推导

这一步是整道题的灵魂。先定义三个距离：

• a：从head到环入口的节点步数
• b：从环入口走到快慢指针相遇点所需步数
• c：从相遇点继续往前走，再次回到环入口所需步数

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

慢指针从head出发到相遇点，走了a + b步。快指针速度是慢的两倍，同时走了2(a + b)步。另一方面，快指针第一次追上慢指针之前，一定已经在环里多绕了至少一圈。假设它总共绕了k圈，那么快指针的总路程还可以表示成a + b + kL。

两个式子相等，得：

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

化简：

a = kL - b

再写成更直观的形式：

a = (k-1)L + c

因为L - b = c。

这个等式说明了什么？从head出发，走a步正好到环入口；从相遇点出发，走c步能回到环入口，如果再多走整数圈，仍然在环入口。所以只要让一个指针从head出发，另一个从相遇点出发，二者以相同速度一步一步走，最终一定会在环入口相遇。

很多初学者看到这个公式会担心：如果k不是1，第二次循环里两个指针会不会一开始就错过？不会。a = (k-1)L + c意味着从头出发的指针走到入口时，从相遇点出发的指针已经走了c步，可能又额外绕了(k-1)圈，两者同时到达入口。它们从不同起点出发，但会在入口处重合。

这里还有一个常被问到的细节：慢指针进入环后，会不会已经走了好几圈才被追上？标准解法中，慢指针进入环时快指针已经先跑了一段，两者相对距离小于一圈，而每轮快追近一步，所以慢指针在环内走不到一圈就会被追上。这一点保证了前面推导中“慢指针走a+b”的合理性。

3.3 用具体例子走一遍全过程

纸上谈兵再多，不如走一遍例子。假设链表是：

A -> B -> C -> D -> E -> C

A是头，C是环入口，环从C开始，经过D、E又回到C。

用快慢指针追踪位置：

第3轮，fast从E跳到C再跳到D，slow从C走到D，二者在D相遇。这里的a=2，b=1（C到D一步），c=2（D到E再到C两步），确实满足a=c。

相遇后，重新拿一个指针p指向head A，另一个指针q指向相遇点D。接下来每次同步走一步：

• p走到B，q走到E
• p走到C，q走到C

两指针在C相遇，C就是环入口。这个例子虽然简单，但能把“为什么还要从头走一次”解释清楚。很多教程直接写代码，省略了这一步，导致读者只记住结论却不知道发生了什么。

4. 代码实现与边界细节

4.1 Python版快慢指针实现

理解了推导，代码就很短了。我常用的写法是：

def detectCycle(head): slow = fast = head has_cycle = False while fast is not None and fast.next is not None: slow = slow.next fast = fast.next.next if slow is fast: has_cycle = True break if not has_cycle: return None p = head q = slow while p is not q: p = p.next q = q.next return p

代码里有三个关键点需要注意。

第一个是while条件里的fast.next判断顺序。必须先判断fast本身不为空，再判断fast.next不为空。如果写成while fast.next and fast，当fast为空时，访问fast.next会直接报错。Python的and是从左到右求值，顺序错了就是空指针。

第二个是“是否同一对象”的判断。链表节点是否相同，应该看内存地址是不是同一个。Python中建议用is而不是==，尤其当节点类可能重写了__eq__时，is才真正符合“同一个节点”的语义。题目没有重写这些方法时两者结果一样，但养成用is的习惯更好。

第三个是第二次循环前一定要有环。我用has_cycle标记来保证进入第二次循环的只有“确实有环”的情况。如果链表无环而强行进入第二次循环，要么使用未定义的slow，要么让p和q在某个时刻比较不存在的节点，最后得到错误结果。

也可以写一个精简版：

def detectCycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: break else: return None p = head while p != slow: p = p.next slow = slow.next return p

Python的while-else在循环没有break时执行else分支，可以直接return None。这个写法更短，但可读性不如显式标记版本。如果是团队协作或者代码评审，我推荐第一个版本，避免后来的人对else语义产生误解。

4.2 C++版实现与内存管理注意事项

C++版本思路一样，只是指针操作更直白：

ListNode *detectCycle(ListNode *head) { ListNode *slow = head; ListNode *fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if (slow == fast) { slow = head; break; } } if (fast == nullptr || fast->next == nullptr) { return nullptr; } while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; }

这里我做了个小改动：相遇后直接把slow重新指向head，再和fast一起走。从结果上看等价，代码更简洁。但它会影响语义理解——slow不再是“相遇点”，而是“新起点”。如果你喜欢保持推导清晰，建议单独定义p和q。我个人更倾向单独定义变量，因为代码维护性更好，别人读起来更容易对应数学推导。

C++的指针比较是地址比较，slow == fast就是判断两个指针是否指向同一块内存，这个语义正好匹配题目需求。需要注意：代码里没有义务释放链表节点内存，因为链表节点是不是由函数分配的都不一定；你只需要返回入口指针，不要顺手delete，否则可能会触发未定义行为。

还有一个工程细节：fast和slow在第一次循环结束后的状态取决于是否有环。因此第二次循环开始前，必须确认是否真的有环。上面代码用fast == nullptr || fast->next == nullptr来判断无环退出，但要小心：如果链表很短且无环，fast最终确实会变成null；如果有环但环的入口不是头节点，fast不会变成null。所以这种判断是安全的。

4.3 五个最容易忽略的边界条件

我在1.2里已经列过边界表格，这里再说五个写代码时经常踩的坑。

第一，空链表。head本身是null，所有指针操作都不能进行。最稳妥的做法是一开始就判断，或在while条件中让fast = head，然后while fast and fast.next自动处理。

第二，单节点自环。只有一个节点而且next指向自己，这种输入在测试数据里很常见。快慢指针第一轮：slow=node->next还是node，fast=node->next->next也是node，二者相遇，第二次循环返回node。算法能正确处理。

第三，入口在头节点。这种情况很多人觉得推导会有问题，因为a=0。代入公式，a=(k-1)L+c，说明从相遇点出发的指针只需要走c步再绕(k-1)圈就能到头节点入口。第二次循环中，head指针和相遇点指针最终会在head相遇。代码不需要特殊分支。

第四，无环但链表非常长。快指针每轮走两步，可能看似“跳过”了好几个节点，但最终会到达null。只要while条件写好，算法一定会退出，不会死循环。但如果在循环里对fast做了多余操作，比如fast = fast->next->next前没有判空，就可能崩。

第五，第二次循环的起点。有人直接把slow重置为head，fast保留在相遇点，然后同步走，这可行。但如果fast还在第一次循环里继续移动，或者slow重置位置不对，就会错过入口。最简单的办法就是严格执行“一个从头，一个从相遇点”。

5. 实际面试中会被追问的点

5.1 为什么快指针移动2步，不是3步

面试官喜欢在代码写完后追问一句：为什么是两步，三步行不行？这个问题考察的是你有没有真正理解追及模型。

慢指针每轮走1步，快指针每轮走2步时，每轮快指针相对慢指针多走1个节点。两个指针在环内沿同一方向前进，相对距离每轮减少1，所以一旦进入追及阶段，它们不会错过，最终必然相遇。如果快指针每轮走3步，相对距离每轮减少2，从数学上看，快指针可能会直接从慢指针的上方“跨”过去，导致二者永远不相遇。

那么快指针能不能走4步、5步？只要相对距离差是1就可以，比如slow走2步fast走3步。但单链表的每一步就是next指针，步数越多，代码越容易在接缝处漏判。实际工程中选最朴素的1和2就够了。这个问题的标准答案是：速度差为1可以保证相遇，2步是代码简练和判断逻辑之间的平衡点。

5.2 环入口的数学证明会不会被要求手推

会。面试官把题目从“环形链表一”升级到“环形链表二”，目的就是看你懂不懂数学推导。如果只是背熟代码，一追问就容易露馅。

我建议你练习推导时，先用小图把a、b、c标出来，再写两个等式，最后得到a=(k-1)L+c。不需要每一步都写到论文级别，但要能用自己的话讲明白：快指针走了两倍慢指针的路程，同时它比慢指针多绕了整数圈，所以从头走到入口的距离，等于从相遇点走回到入口的距离再加整数圈。这就是第二次循环的根据。

如果能顺手解释一下“k=1时，a=c”，就足以证明你理解了。很多面试者把这一句挂在嘴边，但根本不知道k可以大于1。实际上，只要相遇点不同，k可能大于1，但公式依然成立。面试官听到你能主动提这一点，通常会给正面反馈。

5.3 与“环形链表一”的区别和联系

“环形链表一”问的是有没有环，返回布尔值。实现时同样用快慢指针，相遇就返回true，遇到null返回false。它不需要第二次循环，也不需要数学推导，代码更短。

“环形链表二”在前者的基础上增加一个动作：找入口。如果只要求判断有无环，很多看似可行的解法都能用，比如用set记录节点；可一旦要返回节点，set空间代价就显现出来了。因此第二题才会成为经典。两道题一起准备，能看出你对链表双指针的掌握是“会背一道”还是“会一类”。

还可以向外引申一个经典变体：求环的长度。快慢指针相遇后，让其中一个指针停在原地，另一个继续绕圈，等二者再次相遇，走过的节点数就是环长。这个扩展经常被顺嘴问一句，属于性价比很高的加练内容。

6. 常见调试问题与避坑心得

6.1 死循环和空指针问题

链表题最常见的运行结果不是“答案错误”，而是“超时”或“空指针异常”。超时多半是死循环，空指针多半是访问了不存在的节点。

我排查这类问题的习惯是先画图，再在代码里找循环跳出条件。快慢指针的循环跳出条件一般是fast为空或fast.next为空。如果你写的是while slow and fast，slow不会为空，但fast可能为空，这时条件本身没问题。容易出问题的是在循环体里先fast=fast->next->next，再判断fast是否为空，顺序一乱就会在最后一次循环时越过边界。

调试时别习惯性用print打印链表所有节点。如果链表有环，print会永远打不完。我通常用计数器限制打印次数，比如最多打印20轮，或者只打印每一轮的slow和fast值。这个技巧很朴素，但在现场debug时特别能救命。

6.2 快慢指针相遇但入口计算错误

有一种错误很隐蔽：第一次循环里快慢指针相遇后，有人直接把fast或者slow返回。他们觉得“相遇点不就是入口吗”，实际上只有特殊情况下相遇点才等于入口。比如入口就在头节点且a=0时，相遇点可能确实在入口；但入口在中间时，相遇点往往在环的某个任意位置。

还有一种错误是第二次循环的步进不统一。有人让p从头节点，q从相遇点，但循环里p走两步、q走一步，就会错过入口。这里必须严格保持同速。推导中已经证明两个指针同速会在入口相遇，变速就废了。

还见过一种写法：第一次循环相遇后，继续让快慢指针走，直到slow再次等于fast，然后返回fast。这求的实际上是“再次相遇点”，而不是入口。如果环的入口和相遇点不同，这个结果必然是错的。所以写完代码最好用几个不同场景的链表验证，光靠一个用例通过不够。

6.3 从一道题延伸出的工程启示

“环形链表二”虽是一道算法题，但它背后的模型很通用。程序里两个数据之间出现循环引用，就像链表成了环；垃圾回收要检测循环引用，就需要找到“入口”或打破环。缓存的循环依赖、消息队列的重复消费，也可以用类似“记录已访问对象”的思路去排查。

快慢指针本身也不只用于链表。在数组中找重复数字、在流式数据里发现周期序列，都能看到它的影子。把这些题目放在一起练习，你会发现很多题本质上是同一类问题：在一个可能无限循环的结构里，找出循环的发生位置。这个认知，比背一百个模板更能提升算法水平。

我个人刷这道题最大的体会是：不要急着写代码，先把三个距离标在草稿纸上，亲手推一遍等式。推完一遍，快慢指针的所有版本在我眼里都变成同一个模型。后来我再做普通求两个链表的相交节点、反转链表等题目，也习惯用“位置关系”而不是“代码模板”去思考。这个思路可以说是我在链表题上少走弯路的起点。