刷题的人都知道LeetCode上的“环形链表”Linked List Cycle有多经典它不仅是“LeetCode热门100题”里的常客也是各大厂面试手撕代码环节的高频考点。我当年第一次遇到这题时脑子里蹦出的第一个方案就是拿哈希表记录访问过的节点但面试官一句“能不能不用额外空间”瞬间把我问住了。后来我才真正吃透快慢指针Floyd判圈算法背后的数学原理才明白这道题考的不是你会不会遍历而是你有没有“用有限状态解决问题”的意识。这篇题解我会把环形链表这组题目LeetCode 141判断是否有环、142寻找环入口彻底拆开从最直观的哈希表法开始到快慢指针法的完整数学推导再到面试环节里那些不起眼但能加分的细节最后把我刷题时踩过的坑和排查经验一并整理出来。无论你是刚入门的数据结构新手还是准备冲刺周赛的进阶选手这篇内容都能帮你把环形链表这个知识点钉得死死的。1. 问题定义与核心思路拆解1.1 题目到底在问什么先看题目本身。LeetCode 141“环形链表”给了一个单链表的头节点head让你判断这个链表中是否存在环。这里的“环”不是指你代码里定义的循环而是说链表中某个节点的next指针指向了它之前已经出现过的某个节点导致沿着链表遍历会永远走不到尽头。这个概念用生活场景来类比就像你在一座迷宫里走路你以为在往前走结果绕了一圈又回到了同一个岔路口。链表本来是一条笔直的“单行道”但如果某个节点的指针“回头”了整条路就变成了一个“环岛”。判断链表是否有环本质上是判断这条“单行道”有没有变成“环岛”。LeetCode 142“环形链表II”则在141的基础上多问了一步不仅要判断有没有环还要你返回环的第一个入口节点。也就是说如果链表是一个“带尾巴的环”——前面一段是直路后面接了一个圆圈——你需要找到那个“尾巴接上圆圈”的精确位置。这两道题加起来考察的知识点覆盖了链表遍历、双指针技巧、哈希表应用和简单的数学推导属于面试中典型的“一题两问”式考察方式。1.2 核心思路的出发点解决“判断链表是否有环”这个问题我们的出发点其实只有两个方向第一记录的思路。我遍历链表每走到一个节点就把它记下来。如果之后又走到了一个已经记录过的节点那就说明存在环。实现这个思路最自然的数据结构就是哈希表HashSet因为它的查找时间是O(1)。你不需要做任何数学推导只要老老实实地遍历、记录、比对即可。这是最“笨”却最不容易出错的办法也是理解问题本质的第一步。第二追及的思路。想象两个人在操场上跑步一个人跑得快一个人跑得慢。如果操场是环形跑道那么跑得快的人最终一定会从后面追上跑得慢的人。如果把链表的“环”类比成环形跑道让两个速度不同的指针同时从头部出发一旦它们相遇就说明链表中有环。这就是著名的Floyd判圈算法也是这道题能实现O(1)空间复杂度的关键。这两种思路对应两种解法我会在后面的章节里完整拆解。这里先记住一个结论哈希表法重“空间换时间”快慢指针法重“O(1)空间 数学推理”两者各有优劣面试时看面试官想要考察你哪方面的能力。1.3 两种问题形态的关系LeetCode 141和142是递增的关系。一个只会问你“有没有”另一个会追问“在哪儿”。很多同学觉得142难是因为在141的基础上还需要额外的数学推导。但如果你真正理解了快慢指针的相遇过程142的解法就是顺水推舟的事。打个比方141判断的是“这辆火车有没有出轨”而142要找的则是“出轨的点具体在哪个位置”。141只需要一个“是/否”的结论142则需要你精确定位。我们把两道题放在一起讲不仅是因为它们共享同一个数据结构和核心技巧更因为从141到142的思维跃迁本身就是一种很好的算法思维训练。2. 哈希表解法最直观的“足迹追踪法”2.1 思路与代码实现哈希表法的思路极其简单从头节点开始每遍历一个节点先检查这个节点是否已经在哈希表中。如果在说明又回到了之前走过的节点链表中存在环如果不在就把节点加入哈希表然后继续走下一个节点。如果某一步走到了null说明链表遍历到了尽头没有环。这个思路用生活化的语言描述就是“足迹追踪法”。你在迷宫里走每经过一个路口就在墙上画一个标记。如果你发现某个路口已经有了自己画的标记那就说明你在绕圈。C 实现如下class Solution { public: bool hasCycle(ListNode *head) { unordered_setListNode* visited; ListNode* cur head; while (cur ! nullptr) { // 如果当前节点已经被访问过说明有环 if (visited.count(cur)) { return true; } visited.insert(cur); cur cur-next; } return false; } };Python 实现如下class Solution: def hasCycle(self, head: Optional[ListNode]) - bool: visited set() cur head while cur: # 当前节点已经出现过说明有环 if cur in visited: return True visited.add(cur) cur cur.next return False这段代码本身没有任何技巧含量它考的就是你对哈希表底层原理是否熟悉。Set之所以能做到O(1)查找是因为它内部基于哈希表实现通过计算节点的内存地址哈希值来快速定位。注意这里存储的是节点对象本身不是节点的值因为两个不同节点可能拥有相同的值但用对象地址作为唯一标识才能避免误判。2.2 复杂度分析哈希表法的时间复杂度是O(n)空间复杂度也是O(n)。这里的n是链表的总节点数。时间上每个节点最多被访问一次每次哈希表的插入和查找都近似O(1)所以整体是线性的。空间上如果链表中不存在环我们需要存储所有n个节点如果存在环最坏情况下要在环里绕一整圈才能发现重复节点存储的节点数量也不会超过n。所以空间复杂度是严格的O(n)。O(n)的空间在大多数场景下其实已经够用但这道题作为经典面试题面试官几乎必然要追问一句“能不能优化到O(1)空间”这一问就直接把你引向了快慢指针法。2.3 哈希表法的适用场景与局限哈希表法最大的优点是“无脑、直观、不容易写错”非常适合作为面试时的第一反应。如果你的面试官没有额外要求直接写出哈希表法也是一种合格的解法。它同样适用于后续的142题寻找环入口——如果你已经在哈希表中发现了重复节点那么这个重复节点本身就是环的入口。但它的局限性也很明显第一空间复杂度高。当链表特别长时哈希表占用内存不可忽视在嵌入式系统或内存受限的环境中这种解法可能直接不可用。第二它没有触及这道题的核心考点。面试官出这道题往往就是想考察你有没有“双指针”或“Floyd判圈”的意识。如果你只会哈希表可能会被认为算法知识面不够宽。所以我的建议是哈希表法用来保底快慢指针法用来展示实力。你心里要清楚两种解法但最终呈现给面试官的优先是快慢指针版本。3. 快慢指针解法Floyd判圈算法的精髓3.1 快慢指针为什么一定能相遇快慢指针的思路是定义两个指针slow和fast都从head出发。slow每次走一步fast每次走两步。如果链表中存在环那么fast一定会进入环中并最终追上slow如果不存在环fast会先一步到达null终止遍历。这个思路可不可靠我们来稍微严谨地论证一下。当slow进入环的时候假设fast已经在环里转圈了。因为slow速度为1fast速度为2所以每个时间单位内fast相对于slow的速度差是1。也就是说fast在每个单位时间内都会把距离拉近1步。由于环是一个封闭结构fast与slow之间的“相对距离”是有限的。在“追逐”的过程里这个距离不断减小直到减为0也就是fast和slow在同一个节点上相遇。正因为速度差只有1步所以这个相遇过程一定会发生不会出现fast恰好“跳过”slow的情况。这一点非常关键我会在后面的“常见问题”里专门展开讨论。3.2 快指针为什么走2步而不是3步或4步这是一个几乎所有初学者都会问的问题既然目的是追及为什么fast走3步甚至4步不行吗从“能否相遇”的角度说走3步在大多数环结构里也能相遇但存在特殊情况。假设环的长度是mfast的速度是vslow的速度是1那么fast相对slow的速度差是 v−1。如果 v−1 与 m 不互质那就有可能永远无法精确相遇。举一个极端例子环长为2fast走3步、slow走1步时速度差为2与环长的最大公约数是2它们可能一直在错位。而走2步时速度差为11与任何整数都互质所以必然能够相遇。从“安全性”角度说走2步已经是最小且最稳妥的速度差。它既保证了算法必然收敛又不会因为步长太大导致指针跳过整个环而错过相遇节点。很多教科书把这种策略称为“Floyd判圈算法的最小实现”核心原因就是这个“速度差为1”的巧妙设定。3.3 快慢指针的代码实现基于以上原理141题的快慢指针解法可以这样写class Solution: def hasCycle(self, head: Optional[ListNode]) - bool: slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return FalseC 版本class Solution { public: bool hasCycle(ListNode *head) { ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { return true; } } return false; } };这里有一个非常有辨识度的细节while (fast fast-next)这个循环条件保证了fast不会在访问fast-next-next时因为fast-next为null而报空指针异常。也就是说fast指针必须在每一步都能安全地向前迈两步。如果链表是无环的fast会最先到达链表末尾即null循环自然结束返回false。如果链表有环fast永远走不到null它会在环里不断绕圈直到追上slow返回true。从复杂度看快慢指针法的时间复杂度同样是O(n)但空间复杂度从O(n)降为了O(1)。这也是它成为面试标准答案的根本原因。4. 进阶挑战寻找环的入口位置4.1 相遇之后的数学推导当你已经能判断链表是否有环之后LeetCode 142“寻找环入口”就是那道真正区分水平的题目。这题在快慢指针相遇之后还需要一个关键的数学推导。我们来定义几个变量。设链表从头节点到环入口的距离为 a环入口到两个指针相遇点的距离为 b相遇点继续往前走回到环入口的距离为 c整个环的周长为 L显然 L b c。当slow和fast相遇时slow走过的距离是 a b。fast走过的距离是 a b kL其中 k 表示fast比slow多绕了 k 圈环。注意fast的速度是slow的两倍所以在相同时间内fast走过的距离必然是slow的两倍2(a b) a b kL化简一下得到a b kL即a kL − b如果 k 1那么 a L − b c。也就是说从头节点到环入口的距离 a恰好等于相遇点继续往前走回到环入口的距离 c。如果 k 1情况稍微复杂但我们关心的是“头节点到入口”的距离与“相遇点继续走”的距离之间的关系。把 a kL − b 改写成a (k−1)L c因为多绕的 (k−1)L 圈在环内是循环的可以等价于相遇点出发走 c 步就能到达环入口。换句话说不论fast多绕了多少圈从头节点出发走 a 步到达环入口相遇点出发走 c 步也到达环入口。而从头节点出发的新指针和从相遇点继续走的slow指针它们的速度为1必然会在环入口碰头。因此解法就变得清晰在slow和fast第一次相遇后让slow保持在相遇点不动另设一个指针ptr指向head然后让slow和ptr同时以步长1前进。它们相遇的那个节点就是环的入口。4.2 寻找环入口的完整代码class Solution: def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]: slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: # 相遇后从头节点同步出发 ptr head while ptr is not slow: ptr ptr.next slow slow.next return ptr return NoneC 版本class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { ListNode* ptr head; while (ptr ! slow) { ptr ptr-next; slow slow-next; } return ptr; } } return nullptr; } };注意第二个while循环的条件是ptr ! slow二者从不同位置出发但速度一致它们的相遇点就是环入口。这个逻辑严格依赖前文的数学推导如果你没有彻底理解“a (k−1)L c”这一步写代码时会心存疑虑但一旦推导清楚了这段代码就成了自然而然的结果。4.3 边界情况与特殊情况分析在实际运行这段代码时有几个边界情况值得单独检查第一空链表或单节点无环链表。这两种情况会直接导致fast或者fast-next为null循环不进去返回null逻辑正确。第二整个链表就是一个大环。此时头节点本身就是环入口a 0。在相遇后ptr指向headslow在环中某个位置二者最终会在head处相遇返回head依然正确。第三环入口在链表中间位置。这是最常规的情况也是我们上面数学推导覆盖的典型场景。我建议你在本地用这几个构造用例分别跑一遍确认代码行为的稳定性。这不光能加深对算法的理解还能让你在面试时更加自信地回答面试官的追问。5. 两种解法对比与面试加分技巧5.1 复杂度与实现难度全面对比为了让你在面试现场能快速决策该用哪种方案我把两种解法放在同一张表里做对比维度哈希表法快慢指针法时间复杂度O(n)O(n)空间复杂度O(n)O(1)实现难度较低思路直观中等需要理解数学推导是否适合141题适合更适合是否适合142题适合重复节点即入口适合需二次相遇面试加分点稳妥、不易出错展示算法深度和空间优化意识主要风险空间占用高推导不熟练时容易卡壳从这张表能看出一个关键趋势如果你只求“解出来”哈希表法没有任何问题但如果你希望“解得好”快慢指针法几乎是必选的答案。LeetCode的热门100题里环形链表之所以常年上榜恰恰是因为它在“空间优化”这一点上有着极强的教学意义。5.2 面试中如何呈现你的思路面试时千万别上来就闷头写代码。我以一个高频场景为例面试官问“判断链表中是否有环你会怎么做”你完全可以用这样的节奏来回答第一步先说最直观的哈希表法“我可以用一个哈希集合记录访问过的节点如果走到某个节点时发现它已经在集合里说明有环。时间复杂度O(n)空间复杂度O(n)。”第二步主动提出优化方向“但哈希表需要O(n)的额外空间。如果面试官要求空间优化我可以改用快慢指针。慢指针走一步快指针走两步如果存在环快指针一定会在环里追上慢指针如果无环快指针会先到达链表尾部。”第三步说明边界条件“实现时需要注意循环条件确保快指针访问next-next时不会出现空指针异常。所以循环条件要写while (fast fast-next)。”第四步等待面试官追问。如果面试官接着问“怎么找环入口”你就顺势把142题的数学推导完整呈现出来。整套回答逻辑严密而自然完全有“资深候选者”的从容。5.3 一个容易忽略的加分细节我在面试别人的过程中经常发现候选人能写出快慢指针但问到一个问题就卡住了为什么第二次相遇时两个指针一定要以步长1前进如果以别的速度会怎样答案很简单第二次相遇的目的是让两个指针“等速同行”通过距离对齐来找到入口。如果速度不相等它们之间的位移差会引入新的变量推导就直接被破坏了。因此第二次相遇必须严格使用等速这也是Floyd算法中非常微妙的一个点。如果你能在面试中主动把这个细节说出来会比单纯报出代码效果好得多。因为它向面试官传递了一个信号你不只是记住了代码而是真正理解了这个算法为什么这样设计。6. 常见问题与排查技巧实录6.1 空指针异常为什么总在“下一步”爆发很多初学者在实现快慢指针时喜欢把循环条件写成这种形式while fast.next and fast.next.next:乍一看没问题但如果链表是空链表或只有一个节点第一轮循环就会因为访问fast.next而直接报错。正确的做法是先对fast判空再加fast.next的判空顺序一旦搞反就是空指针异常。我的习惯是每次写完循环条件先在纸上手动模拟一遍“链表只有2个节点且无环”的情况确认fast能安全地走到末尾而不会触发空指针。这个习惯在笔试和面试的现场编辑场景里尤其重要。6.2 快指针会不会“跳过去”直接错过慢指针我在讲原理时已经提过快指针每次走2步、慢指针每次走1步速度差为1所以快指针不会跳过慢指针。这里用更具体的方式解释一遍假设某个时刻slow在环中的位置为 xfast在位置 y。由于速度差为1每个时间单位fast相对slow前进1步。它们之间的“距离”会用1、1、1……地递减最后必然变成0。哪怕这个距离在最开始非常大递减的过程也有穷尽的时候。因为环长有限在绕有限圈之后必能碰上。如果你把fast的步长改成3速度差为2与环长可能产生公约数而错过这就解释了为什么“走2步”不是偶然选择而是有数学保证的必然选择。6.3 为什么我的代码在无环链表中会陷入死循环一个经典错误是忘记在循环体内更新slow和fast。如果你的代码长这样你会在无环链表上陷入无限循环while fast and fast.next: if slow is fast: return True # 忘记赋值这里没有任何节点移动 return False这种错误发生在刚学会“检测”但还没有形成肌肉记忆的人身上。解决方式很简单在判断之前先把两个指针都移动到位。一个小的建议是随时把快慢指针的更新代码放在循环体开头确保即使提前return了指针更新逻辑也不会被绕开。6.4 链表值重复时哈希表会不会误判这是一个很多新人会踩的概念坑。他们觉得如果两个节点的值相同哈希表会误判为“已经访问过”。实际上不会因为你存入哈希表的是“节点对象”而不是“节点的值”。在Python中存入set的是对象引用在C中unordered_setListNode*存的是指针地址。即使两个节点的val完全一样只要它们是不同的节点对象在哈希表里就是不同的键。这个点也可以作为和面试官互动的谈资你不需要显式重写节点的hashCode或equals方法因为默认的对象哈希比较的就是内存地址。理解这一点能帮你避开哈希表相关的大坑。6.5 环的入口推导k值不为1时怎么理解有些同学看到 a kL − b下意识以为 k 只等于1然后就会困惑如果 fast 绕了很多圈才追上 slow这个关系还成立吗关键在于我们推导的第二行a b kL。当 k 1也就是fast绕了多圈a b 整体上比一环 L 大。我们把 a kL − b 改写为 a (k−1)L c其中 c L − b。因为 (k−1)L 是环长 L 的整数倍从头节点走到环入口的距离 a等价于从相遇点往前走 c 步再加上完整的若干圈最终还是会在环入口位置停下。所以“等速走后相遇于入口”的结论在 k 取任意正整数时都成立。如果你在面试时能把这个 k1 的情况主动讲清楚面试官大概率会对你的深入理解留下印象。我曾亲眼见过一位候选人靠这一步直接把面试评价从“通过”提到了“优秀”。7. 实操总结与延伸思考环形链表这道题从表面上看是一个基础数据结构问题但它背后牵出的“空间换时间”与“时间换空间”的权衡、Floyd算法的数学优雅性、以及从141到142的思维跃迁都是算法学习中极为宝贵的素材。我个人在实际操作中的体会是这道题值得你隔一段时间就回头重做一遍每次重做都会有不同的收获。最后再分享一个小技巧当你刷完141和142之后可以顺手去把LeetCode上其他双指针题目过一遍比如“删除链表的倒数第N个节点”和“链表的中间结点”。你会发现双指针的核心思路完全相通——它们都是在“单次遍历”的前提下用“速度差”或“位置差”来提取链表的结构信息。这种触类旁通的感觉远比你机械地刷完100道题更值得追求。