企业官网建设流程全解析

如果你在LeetCode上刷到第141题“环形链表”，第一反应大概是：这题有什么难的？三行代码就能写完。可真正在面试里被这道题拦住的人，从来不是写不出“判断有没有环”的代码，而是被追问“为什么快慢指针一定会相遇”时哑口无言。我当年也一样，AC了141题之后去刷题解区，看得一愣一愣，后来把142题“环形链表 II”也练透，才发现这组题的精华根本不在判断，而在数学推导。

这一篇就把环形链表系列彻底讲透，从141题的快慢指针模板，到142题环入口的证明，再到我刷题时踩过的坑和面试里怎么把推导讲清楚，全部写给你。

1. 这道题到底在考什么：从题目表象到核心考点

1.1 题目原文与基本印象

LeetCode 141题“环形链表”的题目描述短到让人怀疑自己看错了：给你一个链表的头节点head，判断链表中是否有环。如果链表中存在某个节点，可以通过连续跟踪next指针再次到达这个节点，就说明链表中有环，返回布尔值即可。

官方难度标签是“简单”，但它在面试中的出现频率却常年排在前列。在LeetCode题解区，环形链表的题解一抓一大把，高产博主们甚至能用好几篇长文把快慢指针讲出花来。之所以这么多人写，是因为这题在算法面试里的出镜率实在太高，而“简单”只是表象，真正能答好的人并不多。

表面上看，这题只考察链表遍历：沿着next一个个走，如果走到null就说明链表有尽头，没环；如果一直走不出去，就有环。但如果你真的只在代码里写了这么一个遍历循环，你会发现一个问题：怎么知道“一直走不出去”？没有终点标志，程序永远不会自己停下来。所以这道题真正的难点，在于如何在有限步内判断一个可能无限循环的结构，这才是它被归为经典题的原因。

1.2 隐藏在“有环”背后的真实考点

第一层考点是数据结构基本功：链表节点的引用关系、指针移动、循环终止条件的控制。这一层大多数人都能过关，毕竟链表遍历是入门操作。

第二层考点是空间复杂度意识。判断有没有环，最朴素的想法是用哈希表记录访问过的节点，这个方案能通过测试，但面试官紧接着就会问：能不能把空间复杂度降到O(1)。这时候快慢指针的价值就体现出来了，它只需要两个指针变量，不需要任何额外容器。

第三层才是真正的分水岭：数学理解。如果你只知道快慢指针模板，却说不出“为什么一定会相遇”，面试官大概率会怀疑你是背的答案，而不是自己推导出来的。这一层能拦住一大批人。所以我认为，环形链表的真正考点不是代码，而是Floyd判圈算法背后的数学。

1.3 141和142的递进关系：判断是热身，定位才是正餐

141题只问“有没有环”，答案是布尔值；142题“环形链表 II”则要求返回环的入口节点。判断存在与否很简单，但定位入口需要你彻底理解环的结构：链表头到入口的距离、环的周长、入口到相遇点的距离，三者之间存在精确的数量关系。

我把这组题比作看病：141题相当于医生告诉你“体内有结石”，142题则是要精确指出结石在哪个位置。前者靠仪器扫一遍就能定性，后者需要建立完整的内部结构图。刷题时我强烈建议直接把142题当作重点，因为只要142题的推导吃透了，141题就是它顺手白送的小弟。

2. 快慢指针的数学原理：为什么两个指针一定会碰面

2.1 先建立直觉：操场上的追人游戏

假设你和一个朋友在圆形跑道上跑步，你跑得慢，每秒1米，他跑得快，每秒2米。他从后面出发，一开始可能离你有段距离，但只要跑道是闭合的，他一定能追上你。原因不用列公式也能想明白：他相对你每秒逼近1米，而跑道长度有限，追完一圈内的距离就够了，不可能永远追不上。

链表的环就是这条环形跑道。慢指针每次走1步，相当于每秒1米；快指针每次走2步，相当于每秒2米。只要链表里有环，两个指针早晚在环上碰面。这个直觉是判断环形链表的核心。

2.2 一步一步推：相遇是有限步内的必然事件

把直觉转成严谨推导其实只需要几行。

假设慢指针刚进入环的那一刻，慢指针在环入口，快指针已经在环内的某个位置。设环的周长为L，此时快指针与慢指针沿着环的前进方向距离为d，d的取值范围是0到L-1。从这一刻开始，每一轮迭代中慢指针前进1步，快指针前进2步。于是每一轮过后，快指针相对慢指针的净距离减少1。经过d轮，这个距离减到0，也就是两者相遇。因为d最大也就是L-1，所以最多L-1轮后必定发生相遇。

这里有个关键前提：链表中确实存在环。如果链表没有环，快指针会先走到null，循环退出，直接返回False，根本不存在“追得上与否”的问题。实际上，只要快指针每次比慢指针多走一步，也就是速度差恒为1，追及就必然发生；快指针每次走2步是最经典的设置，既保证追赶，又不会因为步幅过大而跳过慢指针。

提示：为什么快指针不会“跳过去”错过慢指针？因为快指针虽然一次走两步，但它是连续经过两个节点的，慢指针每次只走一个节点，两者在节点上的到达是连续的，不存在从慢指针头顶跨过去的瞬间。相当于快指针相对慢指针每轮只接近1个单位，而不是每轮跳过1个节点。

2.3 打破几个常见的想当然

我在评论区见过不少误解，挑三个最典型的说一说。

误解一：相遇时快指针一定比慢指针多走了一圈。真相是，多走的圈数不是固定值。如果环的入口离链表头很远，慢指针还没进入环时，快指针可能已经在环里绕了好几圈；如果环很大，快指针也可能在追上时还没绕完一整圈。多走的圈数取决于链表头到环入口的距离、环周长和相遇位置，三者共同决定。

误解二：相遇点一定在环入口处。真相是，相遇点可以是环上任何一个位置。它取决于慢指针进入环的那一刻快指针所在的位置，而这个位置受环外链表的长度影响。所以不要期待用相遇点直接判断入口，那是下一层问题要解决的。

误解三：快慢指针只知道“有没有环”，无法更进一步。这个误解最容易拖慢进步。实际上Floyd判圈算法最大的亮点，是第一次相遇后可以继续推导出环入口的位置，这正是142题的做法。

3. 判断有环的代码实现与边界处理

3.1 141题最简实现：快慢指针版

我先把代码放上来，再逐行解释为什么这么写。

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def hasCycle(head: ListNode) -> bool: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: return True return False

这段代码有几个值得注意的设计点。

循环条件写成while fast and fast.next，而不是while fast，是因为快指针每次要走两步。如果当前节点是None，说明链表为空或已走到尾部；如果当前节点的next是None，说明下一步快指针会走到None，再在循环体里执行fast.next.next就会抛空引用异常。把这两个条件都挡在循环外面是最稳妥的写法。

比较用slow is fast而不是slow.val == fast.val，是因为环的判断关注的是“同一个节点对象”，而不是值相同。链表中完全可能有两个不同的节点携带相同数值，值比较会造成误判。我见过有人用slow == fast，在Python的ListNode默认比较逻辑下这可能退化为值比较，一旦遇到重复值就出假阳性。

从时间复杂度看，快指针最多遍历一遍非环部分，进入环后最多再走L-1轮就能追到慢指针，所以总时间复杂度是O(N)，空间复杂度O(1)。这已经是这类题的最优解。

3.2 哈希表解法：作为过渡方案也要能写出来

虽然快慢指针是最终答案，但了解哈希表方案仍然有用，因为它是最直白的思路。

def hasCycle(head: ListNode) -> bool: seen = set() while head: if head in seen: return True seen.add(head) head = head.next return False

这个办法的本质是给每个访问过的节点留痕。一个节点如果在哈希表里出现两次，说明遍历过程中走回到了已经走过的节点，自然存在环。直观且不易出错，对新手相当友好。

但它的代价是额外空间。每遍历一个新节点，set里就要存一个引用，最坏情况下节点数N个，空间复杂度O(N)。快慢指针则只需要两个引用变量，空间复杂度O(1)。两者在时间复杂度上都是O(N)，差距集中在空间上。实战中处理几十万节点的链表，O(N)的set不是不能用，但面试要考察的恰恰是你有没有意识到并优化掉这个代价。

面试时我的建议是先说哈希表，再说“但空间可以优化到O(1)”，然后引出快慢指针。这比直接甩快慢指针显得更有思考过程，也符合面试官想听“从朴素到优化”的期待。

3.3 空链表、单节点、尾节点自环：边界case逐个过

刷题最怕的是测试用例故意恶心你。我总结了几类绕不开的边界case，你可以直接拿来测自己的实现：

• 空链表：head为None，直接返回False。
• 单节点链表：节点next为None，返回False。
• 单节点自环：唯一节点的next指向自己，返回True。
• 双节点环：1->2->1，第二个节点指回头节点，返回True。
• 长直链加小环：比如100个节点的直线部分接一个3节点的环。

快慢指针写法的好处是这些边界几乎不需要特殊判断，统一的循环条件能覆盖掉。单节点自环时，fast从head出发，循环条件检查fast and fast.next成立，因为fast非空且fast.next指向自身非空；slow走一步还在原节点，fast走两步也回到原节点，is比较成立，返回True。这个case最能验证你对环的理解到不到位。

4. 进阶：找到环入口的数学推导与142题实现

4.1 给路径命名：头到入口、入口到相遇点、相遇点绕回入口

在做142题之前，先把推导需要的三个距离定义清楚。我不画图，直接用文字描述：

• a：链表头到环入口的距离。
• b：从环入口出发，沿着链表的next方向走到快慢指针第一次相遇点的距离。
• c：从相遇点继续沿着next方向绕回到环入口的距离。
• L：环的周长，显然L = b + c。

第一次相遇时，慢指针走过的总路程是a + b。快指针走过的总路程是a + b + nL，其中n是快指针在环内比慢指针多绕的整圈数，n至少为1。这个“至少为1”可以这样理解：fast速度是slow的两倍，在slow进入环之前fast已经在环中走动；当两者在环上同一位置相遇时，fast比slow多跑的路程必然是整个环长的整数倍。后面你会发现n具体是多少根本不重要。

4.2 核心等式怎么来的：a = (n-1)L + c的完整推演

因为fast的速度是slow的两倍，相同时间内的路程也是两倍，所以有：

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

移项合并立刻得到：

a + b = nL

再代入L = b + c，用b和c消去b：

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

这就是那个关键等式：a = (n - 1)L + c。

这个等式的含义是：从链表头走到环入口需要的步数a，恰好等于从相遇点沿着环绕(n-1)整圈再走c步到达入口的距离。也就是说，只要有一个指针从head出发一次走一步，同时让另一个指针从相遇点也一次走一步，它们必然在环入口处第二次相遇。

理解这个推导，比背下代码重要一百倍。因为面试官一旦追问“为什么第二步两个指针要同速走”，你就能直接背出这五行式子，而不是支支吾吾。

注意：很多资料把这个推导简化成“从相遇点到入口的距离等于从head到入口的距离”，严格来说不够准确，应该是“从相遇点绕环若干整圈再走c步到入口的距离”等于a。口头上简化可以，心里要清楚等式里还有一个整数圈的项。

4.3 142题完整代码与一个具体例子的手算模拟

有了等式之后，实现就非常简单：

def detectCycle(head: ListNode) -> ListNode: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: # 第一次相遇后，新指针从头部出发，slow从相遇点出发 ptr = head while ptr is not slow: ptr = ptr.next slow = slow.next return ptr return None

我拿一个比较有代表性的例子手动走一遍。

构造链表：1 -> 2 -> 3 -> 4 -> 5，其中节点5的next指向节点3，也就是环入口在3，环长L = 3，即3->4->5->3，链表头到入口距离a = 2。

快慢指针从head出发：

• 第一轮后：slow在2，fast在3。
• 第二轮后：slow在3，fast在5。
• 第三轮后：slow在4，fast在4，二者相遇于节点4。

此时b = 1，c = 2，n = 1，验证a = (n-1)L + c = 0 + 2 = 2，成立。

第二步，ptr从head（节点1）出发，slow从节点4出发，都一次走一步：

• ptr到节点2，slow到节点5。
• ptr到节点3，slow到节点3。
• ptr is slow判定成立，返回节点3，这正是环入口。

这个例子环小，看着几乎是一眼看出答案；换成环外部分几十个节点的大链表，流程完全一致，只是需要多走几十步而已。142题整体的时间复杂度仍然O(N)，空间复杂度O(1)，因为两个阶段的总步数都不超过节点总数。

5. 我的刷题经验：从理解到能讲清楚面试

5.1 高频踩坑点：循环条件、移动顺序、值比较

第一坑是把循环条件写成while fast.next或while fast。链表没有环时，快指针很可能走到最后一个节点，这时再访问fast.next.next就是空引用异常。记住，只有同时保证当前节点和下一个节点非空，才可以安全地走两步。

第二坑是移动顺序错误。有人习惯先把两个指针初始化在head，然后先判断“是否相等”再移动，结果第一轮就误判成有环，因为slow和fast初始都指向同一个节点。正确顺序永远是先移动，再判断。

第三坑是用值而不是对象身份比较。两个不同节点的val可能相等，如果环恰好没有出现在这两个节点处，值比较会给出错误的True。用is或重载为引用比较的方式，确保比较的是节点身份。

还有一个不算坑但需要提的骚操作：有人遍历时把每个节点的next改成指向自己，用“是否访问过”来判断环。这个思路判断环本身可行，但会破坏输入链表，面试官通常不会接受，工程中也绝对不能这么干。我建议你提都不要提，除非你能在说出口的同时立刻补充“这是错误示范”。

5.2 面试回答的正确节奏：两分钟讲完一整套

我参加过不少面试，也模拟过不少次。这道题的高分回答节奏大概是这样的：

第一步，30秒说思路。先提哈希表是可以做的，但空间O(N)，然后说用快慢指针可以做到O(1)空间。

第二步，40秒说正确性。慢指针进环后，快指针已经在环内，两者距离小于环长L，快指针相对慢指针每轮逼近1步，所以L轮以内必然相遇。

第三步，30秒写代码。把141题的实现写在白板上，注意循环条件和is比较。

第四步，40秒说扩展。如果面试官问142题，就补充：第一次相遇后，令一个指针从head出发，slow从相遇点出发，同速前进，第二次相遇点就是环入口，因为a = (n-1)L + c。

这套节奏练顺之后，你会发现环形链表这组题真正考察的不是“会不会写”，而是“能不能在几分钟内用清晰的逻辑说服面试官”。而这恰恰是日常刷题时最容易忽略的训练。

5.3 一变三：环长度、链表相交、入口定位都可以复用

吃透环形链表后，你会发现好几个常考题都共用同一套思想。

求环长度：先用快慢指针找到相遇点，然后让一个指针留在相遇点，另一个指针从相遇点出发，边绕边计数，再次回到相遇点时走的步数就是环长。原理很简单，相遇点本来就是环上的点，从环上任意一点绕一整圈回到原点，路程恰好是环周长。

判断两个链表是否相交（LeetCode 160）：可以把链表A的尾节点接到链表B的头节点上，然后跑环形链表的判断。如果A、B相交，那么从交点开始的后缀会被A的尾部接成环，环的入口就是交点；如果两链不相交，则不会成环。用142题的detect方法找到环入口后，再把被改动的next指针恢复成None，就能既得到答案又不污染原链表。

这些都是环形链表母题的分支，理解了入口推导，上面的变种基本不用额外背代码。

我在实际刷题中的体会是，环形链表这组题非常适合用来检验“背答案”和“真理解”的差别。如果你能不看代码，在纸上完整写出a = (n-1)L + c的推导过程，并且能随口说出“从相遇点到入口的距离是c，加上若干整圈仍然到入口”这句话，说明你真正拿下了它。我建议所有刚开始刷LeetCode的朋友，把141和142连在一起练，先写代码，再画图，再给一个完全不懂算法的人讲一遍。这个过程做完，这组题基本就长在你脑子里了。

最后再分享一个小习惯：我每次复习链表题，都会把常见的边界case，比如单节点自环、双节点回环、长链接小环，统统手动模拟一遍，确保没有遗漏。环形链表这个坑我当初踩了不止一次，希望这篇题解能帮你少走弯路。