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在环上的位置记为pfast在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/1423.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 FalseC版本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 xk是绕的圈数至少为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 复杂度与代码对比表题目解法时间复杂度空间复杂度关键点141哈希表O(n)O(n)先查后存第一个重复节点141快慢指针O(n)O(1)while条件防空指针142哈希表O(n)O(n)第一次重复即入环点142Floyd二次相遇O(n)O(1)第二阶段都走一步顺便提一句快慢指针看起来比哈希表复杂但实际上它的常数非常小两个指针交替移动循环次数也不会超过链表节点数加环长的一个常数倍。实际跑起来在超长链表上差距会非常明显——哈希表要维护一个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初始化的两种流派网上刷题的时候会看到两种写法写法Aslow fast head然后先移动再判断。写法Bslow 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)。当v2时相对速度是1距离减小过程是连续的必然相遇当v3时相对速度是2如果某时刻d1那么一轮后d 1 - 2 -1相当于快指针跨过了慢指针。有人会说跨过去后继续追不就完了确实如果跨过去之后两者还在同一个环里理论上后续还可能追上。但这不是必然事件。你可以构造一个环长为2的环慢指针在位置A快指针在位置BB在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到二次相遇证明每一步都是在反复锤炼你对链表是引用结构这回事的直觉。把它吃透后面再遇到链表双指针题你会觉得异常的顺。