环形链表题解：快慢指针Floyd判圈算法详解与证明

1. 环形链表的题面与直觉：这题到底在卡什么

1.1 题面一句话概括

我给自己立的flag是每天雷打不动刷一道算法题，这个系列就叫"算法重生录"。今天轮到环形链表，LeetCode上141和142两兄弟，一个判环，一个找环入口。题目本身不长：给定一个链表的头节点head，判断链表中是否存在环。所谓环，就是某个节点的next指针指回了它之前的节点，导致遍历永远走不到null。

很多同学第一次看到这题的反应是：这有什么难的？我用一个Set把走过的节点全记下来，走一步记一步，如果某个节点第二次出现，那不就是绕回来了嘛。确实，这题暴力解法人人能写，但它之所以能成为面试高频题，恰恰是因为它有一个看起来非常"玄学"的优化解法——快慢指针，也叫Floyd判圈算法。这个解法空间复杂度只有O(1)，背后藏着一套完整的追及问题证明，面试官特别爱在这个点上往下追问两三层。

1.2 哈希表解法：没有技术含量但很稳

先把最朴素的思路写出来。用Python的话，核心逻辑就十几行：

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

这里有一个小细节值得提一下：判断和插入的顺序。先用if head in seen查，再seen.add(head)，这个顺序虽然看起来无所谓，但其实更符合直觉——只有当你"再次遇到"一个节点时才算撞环，而不是第一次遇到就算。如果你把顺序写反：

seen.add(head) if head in seen: return True

第一次循环会把head加进去，接着检查head in seen必然为True，然后直接返回True——链表第一个节点就"判环"了，这显然是错的。至少得把检查放在下一轮循环里，但那样逻辑绕，不如先查后存干净。

哈希表解法再往下说一层：它能判环，但不能直接回答142那道题——环的入口到底在哪。当然你可以这样做：在哈希表里存节点，第一次发现"这个节点已经存在"时，那个节点就是入环点。因为环上第一个被重复访问的节点，必然是从环外第一次踏进环的那个点。这个思路也能做142，空间复杂度还是O(n)。

1.3 面试官真正想听的东西：空间复杂度

你把这个哈希表解法讲完，面试官大概率会点头，然后问一句：能不能把空间复杂度降到O(1)？

这才是这道题真正的考点。哈希表解法的本质是"用额外空间记住走过的路"，那如果我不想用额外空间，该怎么办？答案就是让两个指针在链表上跑，一个快一个慢，利用速度差来判断是否陷入循环。这不只是环形链表这一道题的解法，它背后是一整套"链表双指针"的方法论。后面你会发现，找链表中间节点、找倒数第K个节点、判断回文链表，全都是同一个套路在不同场景下的变形。

所以，刷这道题的时候别只满足于AC，最好把证明过程吃透。我见过太多候选人能背出代码，但被问到"为什么快慢指针一定能相遇"的时候就卡壳了。下一节，我就把这个问题彻底讲明白。

2. 快慢指针的核心证明：为什么一次追两步，就注定能碰到

2.1 相对运动视角：把追及问题变成距离递减问题

先描述一下标准解法：定义两个指针，slow和fast，都从head出发。slow每轮走一步，fast每轮走两步。如果链表无环，fast会先一步走到null，直接返回False；如果有环，fast最终会在环里追上slow，两者指向同一个节点，返回True。

“快的跑得快，所以迟早追上”——这句话对，但不严谨。关键在于，fast和slow并不是在一条直线跑道上跑，而是在一个环里做追及运动。我们可以换个视角：不看绝对速度，只看相对速度。

每一轮循环结束后，slow前进了1步，fast前进了2步，所以fast相对slow来说，每轮只靠近了1步。也就是说，如果我们把坐标系固定在slow身上，fast正以"每轮1步"的速度向slow靠近。

环的长度是有限的，假设环长为b，那么环内任意两点之间的距离（按前进方向）一定在0到b-1之间。既然每轮距离严格减1，那么最多在b轮以内，距离就会归零，也就是两者相遇。一个最简单的类比：你在环形跑道上慢跑，你朋友以比你略快的速度从后面追你，只要跑道是环形的，他总能追上你，因为你们之间的距离每秒钟都在缩小。

2.2 会不会恰好跳过？不会，因为间距变化是连续的

有一个非常常见的疑问：fast一次走两步，那它会不会恰好从slow头上"跨"过去，永远碰不到？

我们仔细推演一下。假设某一时刻，slow在环上的位置记为p，fast在slow前方（沿前进方向）距离d的位置。注意，d是一个整数，范围是[1, b-1]，因为如果d = 0，它们就已经相遇了。

下一轮循环：slow前进1步，fast前进2步。新的距离d' = d - 2 + 1，也就是d - 1。关键点在这里：d每次只减1，从d到d-1，它不可能跳跃。所以当d = 1时，再走一轮，d'变成0，两者恰好相遇——fast落下时正好落在slow所在的位置，而不是跨过去。

如果快指针一次走3步呢？那d' = d - 2，当d = 1时，d'变成-1，也就是fast一下子超过了slow一个身位，两者错过去了。当然，它们后面可能还会再相遇，但这不再是"必然"了，需要额外证明。这就是面试官常用来变体的点，后面我会专门讲。

2.3 一个重要推论：第一次相遇前，慢指针不会走满一圈

这个结论很多资料里没有明说，但它对理解142题的"找环入口"非常重要：在有环的情况下，慢指针入环后，走不完一整圈，就会被快指针追上。

为什么？因为当slow刚到达环入口时，fast已经在环内了。设环长为b，此时fast距离slow（沿前进方向）的最大可能值是多少？最多是b - 1（如果fast正好在slow前一格），最小是1（如果slow入环时fast就在它后面一格）。

而我们已经证明，fast相对slow的速度是每轮1步，所以追上所需的最大轮数就是b - 1。也就是说，在slow前进b-1步之内，两者必然相遇。注意，slow走b-1步，意味着它还差一步才走完一圈。所以第一次相遇点，一定位于环入口之后、但还没绕完一圈的某个位置。

这个推论为什么有用？因为如果你知道第一次相遇发生在慢指针入环后的第x步（0 <= x < b），那么慢指针总共走过的距离就是"链表头到环入口的a步 + 环内的x步"。这个等式是推导入环点的起点。

3. 两版代码拆解：判环与找环入口（141/142）

3.1 141判环：核心逻辑只剩三行

判断环的代码，几乎所有解法都是同一套模板：

def hasCycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False

C++版本：

class Solution { public: bool hasCycle(ListNode *head) { ListNode *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) return true; } return false; } };

有三个细节必须注意：

第一，循环条件是while fast and fast.next，不是while fast.next。原因很简单：如果链表是奇数个节点，fast会停在最后一个节点上，此时fast.next是null，再访问fast.next.next就直接空指针异常了。如果链表是偶数个节点，fast会走到null，此时连fast.next都不能访问。所以条件里必须同时检查fast和fast.next。

第二，判断相等必须放在移动指针之后。如果放在移动之前，初始状态下slow == fast == head，链表哪怕没有环也会直接返回True，那就全错了。

第三，如果链表没有环，fast会先一步到达链表末尾，循环正常结束，返回False。这里不需要额外处理空链表的情况——head为null时，while条件直接不成立，返回False，天然安全。

3.2 142找入口：Floyd判圈的二次相遇

142题在141的基础上多了一个要求：不仅要判断有没有环，还要找到环的入口节点，如果没有环则返回null。

解法分两个阶段：

第一阶段：和141完全一样，用快慢指针找出第一次相遇点。

第二阶段：把fast（或slow）重新指向head，然后两个指针都以每次一步的速度往前走，当它们再次相遇时，相遇的那个节点就是环入口。

代码：

def detectCycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: # 第一次相遇，进入第二阶段 ptr = head while ptr != slow: ptr = ptr.next slow = slow.next return ptr return None

第二阶段为什么成立？这是环形链表最经典的数学证明，我在这里把它完整推导一遍。

设：

• a：从链表头到环入口的距离（节点数）
• b：环的长度（环内节点数）
• x：慢指针入环后到第一次相遇点走过的距离

第一阶段中，慢指针一共走了a + x步。快指针的速度是慢指针的两倍，所以快指针一共走了2(a + x)步。

快指针走的距离，从另一个角度看是什么？它先走了a步到达环入口，然后在环内绕了若干圈，再走了x步到达相遇点。等价于a + k * b + x（k是绕的圈数，至少为1）。所以：

2(a + x) = a + k * b + x

化简：

a + x = k * b

再移项：

a = k * b - x

这个式子可以进一步写成：

a = (k - 1) * b + (b - x)

现在看b - x是什么。环内从相遇点继续往前走b - x步，你恰好能回到环入口——因为从入口走到相遇点是x步，从相遇点走完剩下的b - x步，正好绕环一整圈回到入口。

于是，第二阶段中，ptr从head出发走a步到达环入口；与此同时，slow从相遇点出发，它走了a步，等价于绕环(k-1)圈之后再走b - x步——落点恰好也是环入口。两者在入口处相遇，这个节点就是答案。

这个证明顺下来，142题就不需要背代码了，你随时可以现场推出来。

3.3 复杂度与代码对比表

顺便提一句：快慢指针看起来比哈希表复杂，但实际上它的常数非常小，两个指针交替移动，循环次数也不会超过链表节点数加环长的一个常数倍。实际跑起来，在超长链表上差距会非常明显——哈希表要维护一个Set，插入和查询都有哈希开销，而快慢指针只是两次指针移动。

4. 我踩过的三个坑：空指针、初始化位置和循环条件

4.1 循环条件的空指针陷阱

我第一次写141的时候，代码是这样的：

while fast.next and fast.next.next: # ...

一跑，直接报错。为什么？当链表走到尾时，fast已经是null，取fast.next就空指针了。后来我改成：

while fast and fast.next:

才稳下来。这个fast and fast.next可以说是所有链表双指针题的统一前提：你要访问fast.next.next，就必须保证fast.next不是空；要访问fast.next，就必须保证fast不是空。所以条件的顺序必须是先fast后fast.next，不能反过来。

4.2 fast初始化的两种流派

网上刷题的时候会看到两种写法：

写法A：slow = fast = head，然后先移动再判断。

写法B：slow = head; fast = head.next，然后while slow != fast循环。

两者都可以AC，但写法B的坑更多：你必须先处理head为空的情况，否则head.next直接爆炸；第二个问题是，进入循环后你得想清楚fast已经领先一步了，逻辑上和其他推导不太一致。所以我个人强烈推荐写法A，它最大的好处是"初始位置相同"这件事实，在证明阶段和面试讲解时都特别顺。

4.3 测试用例设计：面试官最爱问的隐藏加分项

代码写对只是第一步。面试官经常会追加一个问题：你打算怎么测这段代码？

我现在的回答模板是：

• 空链表：head = None，返回False/null。
• 单节点链表：[1]，它的next是空，无环；如果1.next = 自身，则有环。
• 长链尾部接环：比如1->2->3->4->5，且5.next = 3，环入口是3。
• 入环点就是头节点：比如1->2->3，且3.next = 1，环入口是1。
• 整个链表就是一个大环：head绕一圈回到head。

尤其最后两个case，很多新手会漏。入环点是head的情况下，第一阶段里slow和fast会在环内相遇，第二阶段的ptr从head出发走0步就已经到达入口，while循环一次都不执行，直接返回head——这正好验证了代码里return ptr的ptr初始值就是head。我见过不止一个同学在讲解142的时候，忘记提这个边界case，导致面试官怀疑他对代码的掌控力。

5. 从环形链表往外看：这一招能打通多少题

5.1 找链表中点（LeetCode 876）

快慢指针最直接的一个应用就是找链表中点。slow走一步，fast走两步，fast走到尾巴时，slow刚好在中点。如果有环，这个思路的前提就被破坏了，所以通常用于无环链表中点。

很多链表面试题的第一步就是找中点。比如"判断回文链表"，进阶做法就是把链表从中点拆成两半，翻转后半段，再逐个比较。你能想到找一个中点需要写多复杂的代码吗？用fast and fast.next循环，三行搞定。

5.2 找倒数第K个节点

另一个常见变形：先让fast走k步，然后slow和fast一起走，当fast走到null时，slow正好指向倒数第K个节点。这也是一个典型的双指针技巧。

这和环形链表有什么关系？思想上是一致的——利用两个指针之间的"距离差"来消除对链表长度的依赖。在不知道链表长度的情况下，你不可能先遍历一遍数出长度再回头找第n-k个节点；但双指针可以一趟搞定。环形链表用速度差，这里用距离差，本质上是同一套工具。

5.3 回文链表（LeetCode 234）与环长度计算

回文链表的O(1)空间解法依赖三步：快慢指针找中点、翻转后半段、逐节点比较。你会发现"找中点"那一步，其实就是876题的解法，而它和环形链表的快慢指针完全同源。

还有一个小变体：如果题目要求"给出环的长度"，怎么做？办法是：用142找到入口后，从入口出发，用两个指针（一快一慢）绕一圈，记录步数。或者，在142的第一阶段，slow和fast相遇后，让fast不动，slow继续以每次一步的速度走，统计走多少步能再次回到相遇点，那个步数就是环长b。这个操作背后的原理，就是第2节里提到的"环长即一圈步数"。

刷题就是这样，一道题打通了，后面三五道题都跟着通了。环形链表的价值恰恰在这里：它不只是让你背下一个Floyd判圈，而是让你掌握"快慢指针"这个真正通用的大招。

6. 面试实战的话术与变体应对

6.1 为什么不要一上来就写最优解

我见过很多面试者，面试官刚说完题目，当即开始写快慢指针。代码倒是没问题，但面试官很难判断你是真的理解，还是背过答案。

更聪明的做法是先给暴力解：用哈希表，O(n)空间。然后自己补一句：“这个解法能过，但空间复杂度是O(n)。如果面试官要求O(1)，还能用快慢指针。”这一句话，既展示了基础能力，又暗示你还有进阶方案。等面试官说“那你写快慢指针吧”，你再开始写，这时你的讲解空间就大多了。

我自己的经验是：面试答题，节奏比答案重要。先抛一个低复杂度方案，再逐步优化，比一次性抛出最优解更安全，因为优化过程就是你讲故事的过程，面试官可以顺着你的思路提问，交流感强很多。

6.2 当面试官问"快指针走三步行不行"

这是高频追问。答案是不一定，需要额外条件。

设快指针每轮走v步，慢指针走1步，则相对速度为每轮v-1步。上一轮如果两者距离为d，新一轮距离变为d - (v-1)。当v=2时，相对速度是1，距离减小过程是连续的，必然相遇；当v=3时，相对速度是2，如果某时刻d=1，那么一轮后d' = 1 - 2 = -1，相当于快指针跨过了慢指针。

有人会说：跨过去后继续追不就完了？确实，如果跨过去之后，两者还在同一个环里，理论上后续还可能追上。但这不是必然事件。你可以构造一个环长为2的环，慢指针在位置A，快指针在位置B（B在A前方一个位置），快指针一次走3步，慢指针走1步，下一轮快指针会走到哪里？你自己推一下就会发现它可能永远和慢指针错位。所以标准答案就是：fast走2步，相对速度为1，间距单调递减，必然相遇；走3步及以上，间距可能非单调变化，无法保证在O(n)时间内相遇。这样回答，面试官就能确认你是真的懂。

6.3 遇到变体题时的分析套路

如果面试官现场出一道没见过的链表题，我的分析顺序是：

一，先看有没有环。题目没说就默认无环，但可以问一句“输入会不会有环”，这往往是坑。

二，想清楚能不能用双指针。凡是需要找位置、找中点、找倒数第K个、找相交点的题，先试试双指针。

三，分析双指针的移动策略。一个关键问题是：两个指针的相对速度差应该设多少？设1（即快指针走两步）通常能保证相遇，设多了可能导致跳过。

四，写代码前先把边界情况说一遍：空链表、单节点、头尾相连、环在中间。

这套思路应付大部分链表题都够用。环形链表作为一个经典模型，它的价值不是让你背下一道题，而是给你一套分析链表问题的思维框。

最后说点刷题心得

“算法重生录”这个系列做到今天，我最大的感受是：环形链表这道题，代码十分钟写完，证明可能要想一下午。但恰恰是那一下午的证明过程，让你从“背答案的人”变成“能现场推导的人”。面试官问的深度是有限的——会写快慢指针的人很多，能讲清楚为什么快慢指针一定相遇、为什么二次相遇找到的是入口、为什么走三步就不行的，就明显少一大截。

如果你想加深理解，建议干一件事：别用LeetCode，自己在草稿纸上画一条链表，标出a和b，把一个具体例子代入143题那个推导过程中。我试过一次之后，这个证明就再也没忘过，而且面试时基本不用想，都是顺着逻辑说出来的。

环形链表这道题，leetcode上的题号是141和142，但它的思维影响力远不止两题。从哈希表到Floyd判圈，从fast and fast.next到二次相遇证明，每一步都是在反复锤炼你对"链表是引用结构"这回事的直觉。把它吃透，后面再遇到链表双指针题，你会觉得异常的顺。