1. 题目长什么样为什么这道题值得反复刷环形链表这道题在LeetCode上的编号是141属于链表专题里最经典的入门题之一同时也是各大厂面试中高频出现的基础题。题目描述非常简洁给定一个链表的头节点判断这个链表中是否存在环。所谓环就是链表的某个节点不是指向null而是指回了链表中的某个更早的节点形成了一个闭环。这题看起来简单真正写起来却容易翻车。不少新手第一次接触时会想我遍历链表把每个节点存下来如果遇到了重复节点就说明有环。这个思路没问题但面试官往往会追问一句如果空间复杂度要求O(1)呢这个时候哈希表方案就失效了快慢指针方案才是真正的考点。我个人的看法是这道题值得反复刷的原因有三个。第一它把链表遍历和数学思维结合在了一起是理解指针操作最直观的入门题。第二它是后续很多链表进阶题的基础比如环形链表II找环入口、链表中环的长度计算、以及一些需要先判断是否有环才能继续求解的复合题。第三它考察的快慢指针思想在数组题目、字符串题目、树题目中都会变形出现比如LeetCode 287寻找重复数、LeetCode 202快乐数本质上都在用同一套追及思想。把这道题吃透等于给后续刷题打了一个非常牢的地基。我见过很多人刷题喜欢追求数量一天刷十道简单题但对每道题背后的思想挖掘得很浅。环形链表这道题就是我反复劝人慢下来的典型代表——它表面上是判断有没有环实际上藏着Floyd判圈算法的完整推导、快慢指针的数学证明、以及边界条件的各种坑。把这些搞清楚比懵懵懂懂刷二十道简单题更有价值。2. 先别急着写代码从暴力法理解问题本质2.1 哈希表法最直观但空间换时间先聊大多数人的第一反应。遍历链表把访问过的节点引用存到一个Set里每到一个新节点就先检查这个节点是否已经存在。如果存在说明链表中存在环如果遍历到了null说明链表没有环正常结束。用Python写出来特别短def hasCycle(head): seen set() cur head while cur: if cur in seen: return True seen.add(cur) cur cur.next return False这里要注意一个关键点Set里存的是节点的引用也就是节点在内存中的地址不是节点的val。很多新手会在这里犯错把val存进去结果遇到两个不同节点有相同值的情况就直接误判了。链表节点是用next指针串起来的判断是否走过一个节点唯一可靠的依据就是节点的内存地址。这个方案的时间复杂度是O(n)每个节点最多访问一次空间复杂度是O(n)最坏情况下要把整条链表的节点引用全部存进Set。在LeetCode 141这道题里数据规模一般不会把O(n)空间卡死提交也能过但面试时如果你只给出这个解法大概率会被追问能不能把空间复杂度优化到O(1)。2.2 为什么哈希表法不够好哈希表方案的本质是用记录所有访问历史来换取确定性。这就像你在一个迷宫里走路每走一个岔路口就在地上做一个标记下次再走到这个路口就知道自己绕回来了。这种方式非常可靠但代价是你得带一大堆标记材料走过的每个路口都要标记一次。如果迷宫特别大标记材料的体积就成了问题。在算法题中O(n)的空间复杂度通常意味着你的解法还有优化空间。面试官问这道题核心就是想考察你是否知道Floyd判圈算法也就是快慢指针。快慢指针不记录任何历史信息只用一个快指针一个慢指针在链表上移动用速度差来检测环的存在空间复杂度直接降到O(1)。从实际面试表现来看能够主动从哈希表法过渡到快慢指针法并且讲清楚两者的本质区别记录历史 vs 数学判定这本身就是一种能力的体现。理解了这一步再看后面的快慢指针推导就不会觉得生硬了。3. 快慢指针为什么两步一定追得上一步3.1 追及问题的直觉理解快慢指针的思路是这样的使用两个指针慢指针slow每次走一步快指针fast每次走两步同时从head出发遍历链表。如果链表中有环那么快指针一定会在某个时刻追上慢指针两者在环中相遇如果链表中没有环快指针会先一步到达null循环结束。为什么快指针一定追得上慢指针用生活中的场景类比一下。想象两个人在一个圆形操场上跑步一个人跑得慢一个人跑得快同一起点出发。只要跑道是闭环的跑得快的人一定会在某一圈从后面追上跑得慢的人。链表中的环就相当于圆形操场快指针的速度是慢指针的两倍所以必然存在一个时刻快指针和慢指针处于同一个节点上。这里面有个容易混淆的点快指针追慢指针并不是第一次经过的时候就追上而是可能已经绕了好几圈。但不管绕多少圈只要环存在快指针相对慢指针的速度是每回合走一步两者同时移动一回合fast走两步slow走一步fast相对slow前进了一步这个相对速度是恒定的所以最终一定能追上。3.2 严谨的数学推导直觉归直觉真要讲给面试官听最好还是能给出一些数学上的依据。假设链表从头节点到环入口节点的距离为D环的长度为C慢指针进入环后走了x步此时快指针已经在环内走了若干圈设它已经走了n圈两者相遇。因为快指针走的总路程是慢指针的两倍可以得到下面的关系式2 * (D x) D x n * C等号左边是快指针走的总距离快指针速度是慢指针两倍、运动时间相同等号右边是慢指针走的距离Dx加上快指针在环内多绕的n圈。化简后D x n * C也就是说慢指针从链表头走到相遇点的距离恰好等于环周长C的整数倍。这个式子是快慢指针算法最重要的基石后面找环入口的推导还要继续用到它。这里顺便解释一个新手常问的问题为什么快指针一定要走两步而不是走三步、四步从数学上看只要快指针每次比慢指针多走一步即相对速度为1在环内就一定能追上所以三步四步在理论上也行。但实现上走两步最简单、最安全因为步数多了以后边界条件更复杂而且每次多走一步实际意义不大。工程上追求简单可靠走两步是公认的标准方案。3.3 代码骨架与终止条件快慢指针的代码框架非常清晰def hasCycle(head): if not head or not head.next: return False slow head fast head.next while slow ! fast: if not fast or not fast.next: return False slow slow.next fast fast.next.next return True注意这里的初始设定slow从head出发fast从head.next出发而不是两者都从head出发。这样做的目的是让循环可以正常进入否则两者初始相等循环体根本不会执行。初始化不同位置但相对速度仍然恒定不影响追及结论。终止条件要仔细检查fast和fast.next都可能为空。如果链表没有环快指针会先走到链表末尾此时fast为None或者fast.next为None说明链表正常结束返回False。如果链表只有一个节点或为空也直接排除。这些边界条件在LeetCode提交时是必测的用例写的时候要格外留意。4. 完整代码实现与核心注释4.1 Python实现给出一个可以直接提交的Python版本代码里我加了详细的注释方便理解每一行的作用class Solution: def hasCycle(self, head: ListNode) - bool: # 空链表或只有单节点不可能成环 if not head or not head.next: return False # 初始化快慢指针让 fast 在 slow 前面一步 slow head fast head.next while slow ! fast: # 如果 fast 走到了链表尾部说明没有环 if not fast or not fast.next: return False # 慢指针走一步快指针走两步 slow slow.next fast fast.next.next # 快慢指针相遇说明存在环 return True时间复杂度O(n)空间复杂度O(1)。这里有个小细节值得说下每次循环快指针走两步之前都要先检查fast和fast.next是否为None很多新手会写成while fast and fast.next:来循环那个写法没有错但上面的写法在逻辑上更紧凑也让相遇判定和无环判定分得更清楚。4.2 Java实现Java版本的思路完全一致只是语法不同public class Solution { 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; } }Java里要特别注意空指针异常fast.next.next这一步在fast或fast.next为空时会直接抛NPE所以一定要先判空再移动。这也是为什么循环体内检查fast和fast.next的状态必须放在移动指针之前。4.3 C实现C写法和Java几乎一样只是指针访问用-class Solution { public: bool hasCycle(ListNode *head) { if (!head || !head-next) return false; ListNode *slow head; ListNode *fast head-next; while (slow ! fast) { if (!fast || !fast-next) return false; slow slow-next; fast fast-next-next; } return true; } };三种主流语言的实现放在一起对比就能发现这道题的语言差异只在空值判断和指针访问语法上核心逻辑完全一致。这也是链表题的一大特点思路定下来之后换语言基本就是照抄结构。5. 进阶一变如何拿到环的入口节点5.1 环形链表II的题目要求LeetCode 142是141的进阶版本题目在判断是否有环的基础上进一步要求返回环的入口节点。如果链表有环需要找到环开始的那个节点如果没有环返回null。这个进阶问题在面试中出现的频率甚至比141还高因为它在快慢指针的基础上加入了数学推导能更全面地考察候选人的逻辑能力。很多刷题者做141的时候觉得简单到142就卡住了。卡住的原因不是代码难写而是缺少对相遇之后怎么做的理解。这个进阶题核心就一句话当快慢指针第一次相遇后把一个指针放回链表头然后两个指针都改成每次走一步再次相遇时所在的节点就是环入口。5.2 环形入口推导的完整过程这个结论看起来很神奇实际上用前面推导的式子一步就能得出。假设链表头到环入口的距离为D环入口到快慢指针第一次相遇点的距离为x环的长度为C。在相遇时慢指针走了Dx步快指针走了Dxn*C步其中n是快指针比慢指针多绕的圈数。由于快指针速度是慢指针的两倍2 * (D x) D x n * C 化简得 D x n * C 即 D n * C - x这个式子的含义是从链表头走到环入口的距离D等于绕环n圈再减去从环入口走到相遇点的那段x。换一种等价的说法如果一个指针从相遇点继续往前走走C-x步就到达环入口另一个指针从链表头出发走D步也到达环入口而D (n-1)*C (C-x)也就是说第二个指针在环里绕了n-1整圈之后再走C-x步也正好到达环入口。所以把两个指针保持同速前进它们必然会在环入口相遇。这就是先快慢指针找相遇点再同速指针找入口的完整数学依据。各位读者如果之前只是死记硬背这个解法现在看完这个推导应该能真正理解为什么代码要这样写了。5.3 找环入口的代码实现def detectCycle(head): if not head or not head.next: return None slow head fast head.next # 第一阶段找相遇点 while slow ! fast: if not fast or not fast.next: return None slow slow.next fast fast.next.next # 第二阶段找环入口 # 注意这里要重新用一个指针从 head 出发slow 保持在相遇点 ptr head # 一个细节因为 fast 初始在 head.next第一次相遇时 # slow 已经比从 head 同时出发的情况多走了半个步长 # 所以第二次循环要让 slow 和 ptr 在同一起跑逻辑上对齐。 # 实际实现中通常写成下列形式 while ptr ! slow: ptr ptr.next slow slow.next return ptr上面代码中我特意注释了初始化对第二次循环的影响。严谨的写法有两种第一种是让fast也从head出发fast head这时候第一次相遇后把fast重置回head然后两个指针都每次走一步相遇即入口第二种是上文中fast从head.next出发的写法需要额外注意逻辑对齐。为了保证代码简单不易出错我更推荐初学者统一使用下面的写法def detectCycle(head): slow head fast head # 找相遇点 while True: if not fast or not fast.next: return None slow slow.next fast fast.next.next if slow fast: break # 找入口 fast head while slow ! fast: slow slow.next fast fast.next return fast让快慢指针都从head出发第一次相遇后把fast重置到head再同速前进相遇点就是环入口。这个版本是最容易理解也最不容易写错的我个人的刷题经验也是这样建议的142题用双指针同起点写法逻辑链最短推导和代码完全对应。6. 进阶二变如何计算环的长度、链表总长6.1 计算环长度的两种思路环的长度C在面试中是个常被追问的延伸问题。第一种思路是在已知环入口节点的情况下从入口出发绕一圈回到入口走过的步数就是环长。第二种思路是在快慢指针相遇后让慢指针保持每次走一步用计数器记录它再次回到相遇点所需要的步数这个步数也是环长。第二种思路的好处是不需要先找环入口仅仅在141的基础上多几行代码就能实现。def cycle_length(head): if not head or not head.next: return 0 slow head fast head.next while slow ! fast: if not fast or not fast.next: return 0 slow slow.next fast fast.next.next # 相遇后让 slow 继续走统计绕环一周的步数 length 1 slow slow.next while slow ! fast: slow slow.next length 1 return length注意这里计数器初始值为1因为slow从相遇点走到下一个节点时已经完成了一步。很多人在这种细节上容易差1建议先拿实际例子手推一遍比如构造一个环长为3的链表走一遍确认结果是3而不是2。6.2 链表总长度的计算知道环入口位置和环长之后链表总长度等于链表头到环入口的长度D加上环的长度C。D可以通过在找到环入口后用一个指针从头出发走到环入口来统计计数器累加即可。在环形链表II的代码基础上这个扩展几乎是免费的def total_length(head): entry detectCycle(head) if not entry: # 无环直接遍历链表数长度 length 0 cur head while cur: length 1 cur cur.next return length # 有环先计算环长 C cycle_length(head) # 再计算头到入口的距离 D D 0 cur head while cur ! entry: D 1 cur cur.next return D C这个扩展版本覆盖了有环和无环两种情况适合在面试时展示你对这个题型的系统掌握程度。但要注意实际面试中不要一上来就把所有扩展都倒出来先答完基础题在面试官追问时再层层深入节奏感很重要。7. 常见错误与调试技巧实录7.1 我亲身踩过的坑环形链表这个题代码量很少但我见过太多人在同一个地方翻车我自己早期刷题时也交过几次红。最常见的坑就是快慢指针初始化不一致。很多人照抄代码却不知道为什么要一个指向head、一个指向head.next结果自己写的时候两个都指向head然后while条件写while slow ! fast发现循环根本进不去程序直接跳过返回了True。实际上如果你想让两个都从head出发就得把循环条件改成while True在内部判断是否相遇或者用其他方式跳出。总之思路和代码框架要对应不能拼凑。第二个高频错误是判断空指针的时机。快指针每次走两步如果链表没有环fast最终会停在最后一个节点上此时fast.next为空如果再执行fast.next.next就会抛异常。我见过很多新手把if not fast or not fast.next写在循环末尾的等于先移动再判断异常已经抛出来了。正确的顺序是先判断-再移动。第三个错误是混淆节点的值和节点的引用。虽然有环的链表一般不会出现两个不同节点值相同的干扰但做哈希表方案时如果你存的是val而不是节点本身哪怕链表没有环只要存在重复值就会误判成有环。这个坑在LeetCode的讨论区里反复出现值得记在心里。7.2 常用的调试手段链表类的题目调试起来比数组稍微麻烦因为链表结构在LeetCode的测试用例里通常是用数组模拟的。我自己调试环形链表时一般会构造一个简单的用例手动画出节点图来核对。比如构造一个四个节点的链表让第四个节点指向第二个节点那么结构就是1-2-3-4-2-3-4... 环入口是节点2环长是3。手动执行快慢指针流程时建议在纸上画一个表格记录每一步slow和fast分别指向哪个节点慢慢走几轮就会非常直观地看到相遇的过程。一个实用的技巧是写一个辅助函数把走过的节点顺序打印出来限制打印次数防止死循环。比如def debug_cycle(head): slow head fast head.next steps 0 while slow ! fast: if steps 20: # 防止死循环 break print(fstep {steps}: slow{slow.val}, fast{fast.val}) slow slow.next if not fast or not fast.next: return False fast fast.next.next steps 1 return True这种打印方式只适合调试不适合提交但它能帮你非常清晰地建立起快慢指针在环里绕圈的动态画面。刷题时建立这种画面感很重要因为只有真正在脑子里模拟出指针的轨迹后面遇到变形题时才能快速联想到这类解法。7.3 快慢指针思想的其他应用最后说点扩展内容。环形链表这道题考的快慢指针思想其实在很多看似不相干的题目里都有变体。LeetCode 287寻找重复数题目说一个长度为n1的数组里数字范围是1到n只有一个数字重复要求不修改数组且只用O(1)空间。这题经典解法就是把数组的值当成链表next指针将数组建模成链表然后找环入口。LeetCode 202快乐数判断一个数是否快乐本质也是快慢指针判断是否有环。这些题目表面上跟链表毫无关系核心思想却完全一样。所以我在给刷题的朋友建议时一直强调不要孤立地刷题。环形链表最简单的实现形式可能只要几分钟就写完了但背后的追及思想、数学推导、边界处理完全可以延伸出一个庞大的题型家族。认真消化这一题远比囫囵吞枣地刷十道题更值。我个人在实际操作中的体会是像环形链表这种看起来很基础的题往往最考验人的耐心和严谨度。把推导写清楚把每个if的时机想明白比写出一个能通过所有测试用例的答案重要得多。希望这篇题解能帮你真正理解它而不仅仅是背住它。