企业官网建设流程全解析

刷题进入到第四天，总算遇到了链表里一个让我觉得“有点意思”的题目。前面几天还在跟数组、滑动窗口较劲，突然转到链表，一开始还挺不适应的，尤其是单链表那种“只能往前不能回头”的遍历方式，很多数组里理所当然的操作到了链表里都会变得别扭。直到碰见环形链表，配合着快慢指针的解法，才有一种“原来还能这么玩”的开窍感。

这篇就专门聊聊快慢指针这个思路，以及它怎么直接解决环形链表的判定和入环点查找问题。代码我会给Java版本，但思路完全通用，C++、Python、Go照着改改就成。不管你是准备面试、刷题，还是单纯在学校上数据结构课觉得链表那章昏昏欲睡，这篇文章都值得你认真看一下。我会把为什么能这样做的底层道理讲明白，而不是让你背模板。

1. 为什么快慢指针能检测环形链表——核心思路拆解

1.1 先把“快慢指针”这个东西说清楚

快慢指针，英文里有个特别形象的说法叫“龟兔赛跑”，在链表相关的题里非常常见。核心操作极其简单：定义两个指针，都从链表头出发，慢指针每次往后走一个节点，快指针每次往后走两个节点。

如果你心里想的只有代码实现，那确实就是这么点事。但关键问题是：为什么一个走两步、一个走一步，就能判断链表里有没有环？如果链表没有环，那快指针会最先碰到null，任务直接结束，说明这个链表是个普通的单向链表。如果链表里有环，那快指针和慢指针迟早会再次相遇——注意，这里说的是“再次”，因为它们在起点也算是相遇过一次。

这两个指针一旦进入环里，就好比两个人在一个圆形操场上跑步，一个速度快、一个速度慢，快的那个人迟早会从后面追上来套圈撞到慢的那个人。这个“追及”过程就是快慢指针检测环的核心依据。

1.2 一个生活化类比：操场套圈

我试着把这个过程讲得更直观一点。假设你和朋友在一个环形跑道上锻炼，你走两步，他走一步，而且两人同时出发。因为他比你快，所以他会慢慢地拉大与你之间的距离。但是跑道是圆的，他不可能是无限远离你，当他跑完一整圈之后，自然就会从你身后追上来。

链表里的“环”就是这个操场。慢指针每走一步，快指针走两步，相对速度是“一步”。一个关键的事实是：只要环存在，快指针相对于慢指针的靠近速度是“每轮靠近一个节点”，那么它一定会追赶到慢指针，哪怕这个环里只有一个节点——如果环里只有那个节点，快指针走两步，慢指针走一步，两人都会反复回到那个节点上，这不叫相遇，这也太刻意了，实际上环长至少为1的情况下快指针第二次到达这个节点时，慢指针刚好第一次到达，之后快慢指针同步，相遇就是必然。

这里面有个隐藏前提：快慢指针都进入了环里之后才谈得上追及。如果环很长，而链表头到环入口的距离也很长，那在慢指针进环之前，快指针可能已经在环里绕了好几圈了。但这没关系，快慢指针相对速度固定，只要慢指针进入环，接下来的事就是时间问题。

1.3 环形链表检测的两个核心事实

我们先理清两个关键结论，后面的代码、推导都会用到：

第一，如果链表无环，快指针会先走到链表末尾的空指针，这个可以当作终止条件。

第二，如果链表有环，则快慢指针一定会在环内的某个位置相遇。

为什么一定会相遇？因为快指针每次比慢指针多走一步，相对于慢指针而言，“距离”在逐渐缩短。慢指针在环内绕圈，快指针也在绕圈，只要时间足够，快指针一定追得上。

听到这里可能有人会想：快指针速度是慢的两倍，会不会出现“刚好跳过”的情况？比如慢指针在节点A，快指针在相邻的节点B，然后一下走到节点C，恰好错过了？

这个疑虑我以前也有，后来专门画图推导过。答案是：不会。因为快指针相对于慢指针的速度是一步一个节点。当快指针距离慢指针还差一个节点时，下一轮操作之后，慢指针前进一格，快指针前进两格，结果就是快指针到达慢指针原来的位置，而慢指针已经走到下一格，两个人刚好相邻——以此类推，在节点层面上它们会“擦肩而过”再“追上”，但不可能是“瞬间穿过”。详细证明只要考虑相对运动即可：追赶速度=1节点/轮，只要环有限，迟早追上。而且由于每次移动的步长是整数，相对距离每轮严格减少1，不存在跳过的情况。

所以在代码里你不需要额外记录环内哪个位置是特殊点，你只需要在快慢指针相遇时停一下，然后利用这个相遇点做后续计算。

2. 环形链表的判定与入环点查找——两道经典题一次吃透

2.1 环形链表基础版：判断有没有环

这道题对应力扣141题。需求就是给你一个链表的头节点，让你判断链表中有没有环。如果只是判断是否存在环，代码其实非常短：

public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; }

这里有个细节值得专门说一下：很多教材里的写法是让快慢指针都从head出发，循环条件是fast != null && fast.next != null，然后每次移动。但我个人倾向于把快指针先往前挪一个位置（fast = head.next），这样做的目的是让两个指针不要一开始就相等，否则while循环会进不去。

如果你想让快慢指针严格从同一个起点出发，写成下面这种形式也可以：

public boolean hasCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { return true; } } return false; }

第二种写法更常见，因为它在快慢指针相遇的瞬间才判定有环，逻辑清晰。两种写法都能用，看个人习惯。我建议刷题的时候固定一种写法，形成肌肉记忆，面试的时候不容易写错。

2.2 环形链表进阶版：找出入环点

判断完有没有环，紧接着就会有一个更难的问题：如果链表有环，环的入口节点是哪一个？这道题对应力扣142题。你不仅要证明有环，还要精确指出从链表头出发走多少个节点就进入环。

这题的代码实现也不复杂，但难就难在为什么可以这样做。

先说结论：先用快慢指针找到相遇点；然后让一个指针从链表头重新出发，另一个指针从相遇点继续出发，两个指针都改为每次走一步；它们再次相遇的那个节点，就是环入口。

public ListNode detectCycle(ListNode head) { ListNode slow = head; ListNode fast = head; // 第一阶段：找相遇点 while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { break; } } // 没有环的情况 if (fast == null || fast.next == null) { return null; } // 第二阶段：找入环点 ListNode ptr = head; while (ptr != slow) { ptr = ptr.next; slow = slow.next; } return ptr; }

这个解法很简洁，但要是说不出背后的数学道理，面试官追问两句就会露馅。所以接下来我重点推导一下。

2.3 关键数学推导：为什么相遇点能帮你找到入环点

我们给链表里几个关键位置取名字。链表头到入环点之间的距离设为a。入环点出发，沿着链表方向走到快慢指针第一次相遇的那个节点，这段距离设为b。从相遇点继续走，回到入环点，这段距离设为c。环的周长是b + c。

当快慢指针相遇时，慢指针总共走过的距离是a + b。那快指针呢？快指针速度是慢指针的两倍，所以相同时间内，快指针走过的距离是2 * (a + b)。但快指针不是一条直线走到相遇点的，它在进环之后可能已经绕了若干圈。假设它绕了n圈（n是正整数，且至少为1），那么快指针的总距离还可以写成a + n * (b + c) + b。

把两个表达式联立起来看：

2 * (a + b) = a + n * (b + c) + b

整理一下：

a + b = n * (b + c)

也就是：

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

这个式子告诉我们一件重要的事：从头节点到入环点的距离a，等于从相遇点出发绕了(n - 1)圈之后，再走一个c的距离。而c恰恰就是相遇点回到入环点的那段距离。

因此，如果一个指针ptr从链表头出发，另一个指针slow从相遇点出发，两者都一次走一步，那么ptr走到入环点的时候，slow也刚好绕完了(n-1)圈回到入环点。两个指针自然就相遇在入环点上。

这里特别解释一下，免得有人绕晕：如果n=1，式子简化为a=c，意思是头节点到入环点的距离等于相遇点到入环点的距离，两个指针从两个位置同时出发，步长一样，肯定在入环点碰头。如果n>1，相当于慢指针多绕了几圈，但因为时间同步，绕圈的部分会相互抵消，最终还是会同时出现在入环点。

理解了推导过程，这题就不再是背代码，而是真的会了。

3. 代码实现细节与常见写法对比——让代码真正能跑通

3.1 为什么循环条件必须写fast != null && fast.next != null

写链表题的时候，最痛苦的事情就是空指针异常。快慢指针里的循环条件尤其讲究。

先想一个问题：快指针每次走两步，它在循环体内部会执行fast.next.next。如果fast.next已经为null，再取fast.next.next就直接抛异常了。

所以循环条件里必须保证两件事：

第一，fast != null，保证取fast.next不越界。

第二，fast.next != null，保证取fast.next.next不越界。

只要这两个条件任意一个不满足，说明链表已经走到头了，不可能有环。

我见过不少人把循环条件写成while (slow != fast)，然后走进循环体再判断快指针是否为空。这样写不是不行，但逻辑顺序一定要对，先判空再移动指针。对于141题的第一种写法，我给出了先判空再移动的版本，那也是常见的。

3.2 哈希表方案与快慢指针方案对比

其实检测环形链表还有一种“暴力但直观”的解法：用哈希集合记录访问过的节点。每遍历一个节点，先看它是否已经在集合里；如果在，说明成环；如果不在，就加进去，然后继续往后走。

代码也很简单：

public boolean hasCycle(ListNode head) { Set<ListNode> seen = new HashSet<>(); ListNode cur = head; while (cur != null) { if (seen.contains(cur)) { return true; } seen.add(cur); cur = cur.next; } return false; }

但这方案有两个明显问题：

一是空间复杂度是O(n)，因为你要额外存储整个链表里出现过的所有节点引用。如果链表足够长，内存消耗会很夸张。

二是它没有快慢指针那种“优雅感”。面试的时候，如果你能用快慢指针做出来，通常会被认为对问题有更深刻的理解。

快慢指针的空间复杂度是O(1)，而且还能直接用于寻找入环点。所以面试里想稳的话，优先快慢指针。

3.3 一个有价值的追问：快指针一定要走两步吗

有的读者可能会好奇：快指针每次走两步是基于什么确定的？走三步行不行？

先说结论：快指针每次走两步是理论最优，因为这样相对速度是1节点/轮，能保证在有限环内必定相遇。如果你让快指针每次走三步，那么快指针相对慢指针的速度是2节点/轮，有可能出现“跳过”相遇点的风险。

举一个极端但实际可能出现的例子：环长为b+c=2，快指针和慢指针都在环内，且快指针在慢指针前方正好两个节点。快指针一次走三步，有可能一步迈过慢指针，然后两个人永远卡在某种错开的状态里。所以“快指针每次比慢指针多走一步”才是最安全的配置。

这也是为什么面试题的标准解里几乎都是快指针两步、慢指针一步，不要自己随意改成三步、四步。

3.4 两个题目的代码对比速查表

时间复杂度的O(n)要注意：即便快指针可能绕了好几圈，但因为慢指针最多走完整个链表的节点数加一圈环，整体上还是线性级别。不用太纠结快指针“多跑了几圈”的事情，它在环形里跑的圈数是有限的，和时间复杂度不冲突。

4. 刷题第四天的实战记录与踩坑经验——我的经验供你参考

4.1 我在调试中踩过的三个典型坑

第一个坑：没有处理空链表和单节点链表。

head == null || head.next == null这种边界条件我一开始经常漏掉。虽然代码在LeetCode上有可能侥幸过，但真实面试的时候边界条件也是评分点，尤其是面试官盯着你的空指针处理时。养成习惯，链表题先检查头节点和头节点的next是否为空。

第二个坑：快慢指针都从head出发时，循环条件写错导致死循环。

我第一次写142题时，直接把141的代码复制过来改，结果while (fast != null && fast.next != null)的判断和if (slow == fast)的位置放错了，导致两个指针一开始就相等，然后走进死循环。

这里要记住一个细节：如果你用141题“先移动后判断”的写法，那么循环条件就是要保证能进入下一步；如果用142题那种“先找相遇点再break”的写法，要先让快慢指针移动，再判断是否相等。

第三个坑：误入“环入口等于链表头”的陷阱。

如果链表头本身就在环上，detectCycle返回的应该是头节点本身。有人会用ptr = head.next来找入口，结果把第一个节点跳过去了。142题第二步里，ptr应该直接从head出发，不要自作聪明地提前走一步。

4.2 常见错误速查表

画图验证这一步真的很推荐。以前我总觉得数学推导看看就懂了，后来发现只有当自己亲手画出一个具体实例，把每一步指针的移动都标出来，才算真正掌握了。你可以随便设一组简单的值，比如链表头到入环点是2个节点，环的长度是3个节点，入环点到相遇点是2个节点，然后模拟指针一步一步移动，看看到底为什么会同时到达入环点。整个过程跑下来，这个推导就长在你脑子里了。

4.3 快慢指针不只用于环形链表

第四天刷完环形链表之后，我发现快慢指针这个思想其实还能用在一堆看似不相关的题上。

最常见的例子是找链表的中点。让慢指针每次走一步，快指针每次走两步，当快指针走到链表末尾时，慢指针正好走到中间位置。这比先遍历一遍算长度、再走一半的做法要省一次遍历。

还有一个经常用的场景：找链表倒数第k个节点。这种题可以用“双指针法”，但不太一样——先让一个指针走k步，然后两个指针同步走，当先走的那个指针到底时，后走的那个正好停在倒数第k个位置。这个思路本质上还是“制造一个固定距离差”。

另外，快慢指针配合“反转链表”还能解决回文链表的判断问题。先用快慢指针找到中点，再反转后半段，然后逐节点比较前半段和反转后的后半段是否相等。这个思路可以把空间复杂度压到O(1)。

甚至在一些数组问题里也有快慢指针的影子，比如“原地去重”这种经典题，本质上是一个指针负责探路，另一个指针负责记录最终有效位置。这也是“快慢指针”思想的一种变体。

4.4 一个更深入的问题：环的起点为什么不能用“第一个重复出现”来判断

有很多人一开始会想：既然有环，那顺着链表遍历下去，肯定会重复经过某个节点。那我能不能用哈希表记录所有节点，第一次遇到重复节点时就认为它是入环点？

这个做法不能保证正确，原因很简单：重复出现的节点一定是入环点吗？不一定。入环点是环的入口，但重复出现的那个节点可能是环里的任意一个节点。因为一旦进入环，所有环内节点都会无限重复，你只能检测到“某个节点出现了第二次”，却无法确定这个节点是不是“第一个进入环的节点”。除非你把链表从头到尾的路径完整记录下来，才能判断谁是最早的重复节点。而这种方法本质上就是哈希表方案，空间复杂度是O(n)。

快慢指针的高明之处在于，它不靠“记录历史”，而是靠位置关系的数学推导直接锁定入环点。

4.5 我现在的做题习惯

第四天过后，我渐渐摸索出一套比较顺的做题流程，写在这里给大家参考：

拿到一个链表题先别急着写代码。第一个步骤永远是画图。我一般只会画最简结构，几个方框加几个箭头，把指针的运动轨迹模拟一遍。第二个步骤是把题目要求的“终止条件”想清楚——这道题里，链表是空的时候怎么办，只有一个节点的时候怎么办，遍历到null算不算结束。第三个步骤才是动手写代码。写完代码之后，我还会再画一次图去“跑”代码，特别是有环的情况，模拟几次移动，确保指针没有越界。

第四天这道题让我意识到，刷题并不只是背题，而是要在脑子里建立一种“动态图景”：你能想象指针在链表中移动的画面，你才能判断一个解法是对是错。快慢指针尤其适合这样学，因为它的每一步移动都很具体，有没有环、走到哪里了，都清清楚楚。

如果你也正处在刷题初期，遇到链表题总觉得抽象，我建议你拿一支笔和一张草稿纸，把链表的每个节点画成小方块，把每个指针画成一个小三角。快慢指针谁在前、谁在后，慢慢走几轮，很多东西就自然通了。这道环形链表题就是那个让你从“背模板”转向“真正理解”的转折点。