环形链表经典解法：快慢指针原理与LeetCode实战指南

最近在刷LeetCode Hot100做到第25题“环形链表”题目标着“简单”但真要我当场把快慢指针为什么能相遇讲清楚还是得愣几秒。这道题是链表双指针的入门必刷题也是不少大厂面试的高频开场题因为代码量不大却能一次性考察链表遍历、指针移动、边界条件、空间复杂度权衡甚至还能顺势延伸到“环的入口位置”这种中等难度问题。这篇文章我会结合自己的刷题记录把题目考点、两种主流解法、常见坑、进阶延伸和面试答题思路一块儿梳理出来新手可以照着代码一步步跟刷过几遍的老手也能当做一个查漏补缺的清单。1. 题目解析与核心考点1.1 题面到底在说什么原题要求很直白给定一个链表判断链表中是否存在环。所谓“环”就是链表里某个节点的 next 指针不是指向下一个正常节点而是指回了链表之前的某个节点导致整个链表形成一个环形结构。如果按照普通单链表的方式从头遍历这个遍历永远不会结束会一直在环里打转。题目的输入是一个普通单链表输出是一个布尔值存在环则返回 true否则返回 false。看起来非常简单但真正要写出一个高效、鲁棒的解法需要想清楚几件事第一怎么不靠修改链表记录状态第二怎么在有限空间内完成判断第三怎么处理空链表、单节点链表这些边界情况。这些恰好就是链表类面试题最喜欢考察的基本功。1.2 为什么这道题能进Hot100Hot100里的题目几乎算是LeetCode上最值得反复刷的100题环形链表能入选并不是因为它难而是因为它是一个非常经典的“代表元”它用最少的代码量把“双指针技巧”和“链表结构特性”这两件事讲明白了。很多更复杂的链表问题比如找链表倒数第K个节点、找链表中间节点、合并有序链表背后都离不开快慢指针的思维。而环形链表正是快慢指针最典型、最容易讲清楚的应用场景。另外这道题的时间复杂度要求也很典型——最优解是 O(1) 空间如果只会开哈希表去记录节点虽然也能通过但面试时往往不够加分。它考察的不只是“能不能做出来”而是“能不能用最优的解法做出来”。1.3 输入限制与样例题目给出了链表节点的定义通常是这样的class ListNode: def __init__(self, x): self.val x self.next None限制节点数范围一般是 [0, 10^4]也就是最多一万个节点。节点值范围一般是 [-10^5, 10^5]。这些限制意味着算法的时间复杂度 O(n) 是完全可以接受的但空间上如果也用 O(n)虽然不至于超时却失去了优化的意义。示例一输入为 head [3,2,0,-4]并且 pos 1表示尾节点指向索引为1的节点输出 true。示例二输入为 head [1,2]pos 0输出 true。示例三输入为 head [1]pos -1输出 false。这里的 pos 是题面里用来描述用例的辅助参数实际函数接收的是链表头节点不会直接告诉你环从哪里开始需要靠算法自己判断。2. 解法一哈希表标记法2.1 思路和实现最容易想到的思路就是“记号笔标记法”遍历链表的过程中用一个集合记录下所有已经访问过的节点。如果某个节点之前已经被记录过说明链表中有环直接返回 true如果整个链表走到了头说明没有环返回 false。为什么不能只记录节点值因为节点值可能存在重复。比如两个不同节点的 val 都为 1如果我用哈希表存的是值第一次遇到 1 就记录第二次再遇到另一个节点值也为 1 时就会误判成有环。所以哈希表里存的一定是节点对象本身Python里就是 ListNode 的实例Java里就是节点引用这样才能保证判重时比较的是“是不是同一个节点”而不是值相等。def hasCycle(self, head: Optional[ListNode]) - bool: seen set() cur head while cur: if cur in seen: return True seen.add(cur) cur cur.next return False这段代码很简单但有个细节值得注意cur in seen这一步在Python里会调用 ListNode 的哈希和相等比较。默认情况下ListNode 对象使用默认的 id 作为哈希值所以两个不同的节点即使值相同也不会被判定为同一个对象这正好满足我们的需求。如果你自己定义了 ListNode 的__eq__方法那就需要格外小心尽量直接使用默认行为否则可能出意想不到的问题。2.2 复杂度与适用场景哈希表法的时间复杂度是 O(n)因为每个节点最多被访问一次集合的插入和查询平均都是 O(1)。空间复杂度是 O(n)因为需要额外存储所有链表节点。这个解法最大的优点是直观、不容易错特别适合作为面试中新手的第一反应。但它的缺点也很明显当链表特别长时哈希表会占用大量内存。在大厂面试里如果题目要求 “尝试 O(1) 空间解决问题”哈希表法就不能作为最终答案。不过先说出哈希表法再自己主动提出优化反而能体现你的分析能力和优化意识这部分我在后面讲面试技巧时还会细说。其实哈希表法的代码里还藏着一个边界如果链表为空cur head就是 Nonewhile 循环直接跳过返回 False不需要单独写if not head判断代码会更简洁。这种小细节在面试时很加分。3. 解法二快慢指针法3.1 核心思路Floyd判圈算法快慢指针法也叫 Floyd 判圈算法是这道题的最优解。思路是让两个指针同时从 head 出发慢指针每次走一步快指针每次走两步。如果链表中没有环快指针会先走到链表末尾此时返回 false如果链表中有环那么两个指针进入环以后快指针一定能在某个时刻追上慢指针此时返回 true。这就像两个人在环形操场上跑步一个人跑得快一个人跑得慢。只要操场是环形的跑得快的人总会在某一圈追上跑得慢的人。如果操场是直线跑道跑得快的人会先跑到终点停下两人永远不可能再次相遇。这里的关键在于快指针每次比慢指针多走一步相当于两个指针之间的相对速度差为“每步缩短1个节点距离”所以它们之间的距离会稳定减小直到减为0也就是追上。3.2 为什么快指针每次走两步而不是三步四步快慢指针的步长选2是标准做法。你可以理解为慢指针速度是1快指针速度是2它们的速度差是1这是最小且最安全的差值。只要速度差是1无论环有多长快指针都能一步一步地缩小与慢指针的相对距离必然追上。如果快指针每次走3步甚至更多速度差会变大虽然“理论上”在环内也可能追上但有几个问题第一代码需要更多的前置判断因为快指针可能一次跳好几个节点容易踩到空指针第二在某些环长和步长的组合下快指针可能永远“跳过”慢指针比如环长为3、快指针每次走4步可能会出现两人一直在不同位置交错但始终不相遇的情况需要满足环长与速度差有约数关系这里不展开。所以为了代码的简洁性和正确性2步是最稳妥的选择也是面试官希望看到的约定答案。3.3 代码实现与逐行注释我日常刷题最常用的是Python直接看代码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 fast: return True return False循环条件是fast and fast.next为什么不是slow and slow.next因为快指针比慢指针先到达链表末尾只要快指针还能往前移动两步就说明当前还可以继续判断一旦快指针走到 None说明链表一定没有环直接结束循环返回 False。这里最容易踩的坑是在fast fast.next.next之前不检查fast.next是否存在。如果链表的某个节点 next 是 None而fast又指向这个节点访问fast.next.next就会直接报空指针异常。所以while fast and fast.next这个条件必须写完整缺一个都不行。Java版本的核心逻辑也是一样的public boolean hasCycle(ListNode head) { ListNode slow head, fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { return true; } } return false; }C版本在处理节点判定时用指针比较逻辑完全一致。这三种语言的代码几乎可以互相翻译说明这道题考的不是语言而是思路。实际面试时建议你至少熟练掌握其中一种语言并且能一边写一边解释为什么会相遇。3.4 复杂度与空间优势快慢指针法的时间复杂度是 O(n)。无环时快指针走完整个链表步数约为 n/2有环时慢指针进入环之前最多走 n 步进入环后最多再走环长那么多步就会相遇所以总步数仍然是 O(n) 量级。空间复杂度是 O(1)只使用了两个指针变量不会随着链表长度增长。这个空间优势是哈希表法无法比拟的。在链表节点达到上万甚至更多的时候哈希表法需要分配一套哈希结构快慢指针法却一直是两个指针在跑。这也是为什么它成为标准答案的核心原因。4. 边界条件与常见坑4.1 空链表和单节点链表的判断空链表和只有一个节点且节点 next 为 null 的链表显然都没有环直接返回 false。在快慢指针代码里这两种情况都会被循环条件自然处理掉空链表时 fast 为 None循环不进入单节点时 fast 不为 None但 fast.next 为 None循环也不进入。所以代码里不需要额外写if head is None or head.next is None写了反而显得啰嗦。很多新手会怀疑“单节点链表如果它自己指向自己岂不是有环”这种情况确实存在比如head.next head。此时 fast 和 slow 都指向同一个节点但循环条件fast and fast.next是成立的进入循环后slow 走一步还是指向自己fast 走两步还是指向自己于是slow fast成立返回 true。这个情况可以被正确处理。4.2 节点值重复的“坑”哈希表法里如果误用值作为键会误判。举一个具体例子链表是1 - 1 - null两个节点值都是1但没有环。如果用值集合遍历第一个节点时把1加入集合遍历第二个节点时发现集合里已经有1了就错误地返回 true。正确的做法是存节点对象或者用节点本身作为键。这也是我在本地调试时踩过的真实坑后来我干脆写了一个辅助函数专门构造带环链表来验证两种解法的差别。4.3 while循环条件不能写错快慢指针的循环条件把while fast and fast.next写成while fast.next and fast.next.next行不行当链表为空时fast是 Nonefast.next直接报错所以不行。写成while slow and slow.next行不行如果链表没有环但很长slow 移动得慢快指针可能已经越界访问了而循环还没结束依然会报空指针。所以标准写法就是while fast and fast.next这是经过大量实践验证的同时也是最简单清晰的。4.4 本地如何构造带环链表去测试LeetCode上不需要自己构造输入函数接收的 head 已经由测试用例准备好了。但本地调试时我们需要自己写辅助函数来模拟带环情况。给出一个简单示例def create_linked_list_with_cycle(arr, pos): if not arr: return None head ListNode(arr[0]) cur head nodes [head] for val in arr[1:]: cur.next ListNode(val) cur cur.next nodes.append(cur) if pos ! -1: cur.next nodes[pos] # 让尾节点指向链表中的某个节点 return head这个辅助函数一次性生成了链表并根据 pos 构造环。测试时可以直接调用再配合快慢指针函数验证结果。我建议你一定要自己跑一遍把 pos-1、pos0、poslen(arr)-1 这些情况都试一下理解环在哪接入的对之后做环形链表II会非常有帮助。5. 进阶拓展找到环的入口5.1 环形链表II的题意LeetCode 142题“环形链表II”是这道题的直接升级版不仅要判断是否有环还要返回环开始进入的节点。如果没有环返回 null。这个题在面试中出现的频率同样很高而且非常考察数学推导能力。其实只要理解了快慢指针的相遇过程入口问题并不难。假设链表头到环入口的距离为 a入口到快慢指针第一次相遇点的距离为 b相遇点继续走回入口的距离为 c那么环的周长就是 bc。5.2 相遇后如何找入口当快慢指针第一次相遇时慢指针走了 ab 步快指针走了 a n*(bc) b 步其中 n 表示快指针在相遇前已经绕环走了 n 圈。因为快指针速度是慢指针的两倍所以2 * (ab) a n*(bc) b化简后得到a (n-1)*(bc) c这个式子的含义很巧妙a 的长度恰好等于从相遇点开始继续走 c 步再绕环若干圈的总长度。换句话说如果此时把快指针重置回 head然后快慢指针都改为每次走一步它们最终会在环入口处相遇。实现起来也非常简洁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 fast: slow head while slow ! fast: slow slow.next fast fast.next return slow return None这段代码是环形链表I的最优解代码的延伸几乎一模一样的循环体只多了相遇之后的一小段同步移动逻辑。所以把基础题吃透再做进阶题会觉得自然很多。5.3 为什么这道基础题值得反复打磨很多刷题者容易犯一个毛病追求题量却很少停下来想“为什么”。环形链表这道题恰恰是练习“为什么”的好素材。你可以问自己哈希表法为什么空间复杂度高快慢指针为什么可以相遇步长为什么取2相遇点与入口有什么关系这些问题哪怕只在脑子里过一遍也会让你对链表题的敏感度提高一个层次。后续做“找相交链表”、“判断回文链表”时双指针的思路都能顺畅迁移。6. 实操经验与面试技巧6.1 我在刷这道题时踩过的坑第一次做这道题我用的是哈希表法因为最直观很快就写完了。当时我觉得题目很水就跳到下一题了。直到后来面试问到环形链表II我才发现自己根本说不清为什么快慢指针相遇后再同步走就能找到入口。当场只好硬背答案被追问一句“为什么”就卡住了。所以如果你是真心想把题刷透我强烈建议你在过这道题时多做一步自己画一个5个节点的链表其中环从第2个节点开始手工模拟快慢指针每一步的移动直到相遇。这个过程花不了10分钟但对理解双指针的威力帮助极大。后来我做很多链表题时脑子里都会自动浮现出指针跳动的画面解题速度快了不少。6.2 面试时应该怎么答如果面试官让你写环形链表不要一上来就闷头写最优解。你可以先说“最直接的思路是用哈希表记录访问过的节点时间O(n)空间O(n)。如果要优化空间可以用快慢指针空间降到O(1)。” 这样既展示了基础又展示了优化意识。写代码的过程中面试官常会打断你问“快慢指针为什么一定会相遇”这时你可以用“环形操场两个人赛跑”的类比来解释同时补一句“因为每次快指针比慢指针多走一步所以两者距离会逐步缩短到0”。如果面试官追问“步长为什么是2”你可以回答“步长差为1最稳妥既能保证追赶速度又不会跳过慢指针而且代码只需要判断fast.next”。这套回答基本可以把这道题吃透。6.3 和Hot100其他链表题一起练Hot100里链表题虽然不多但每一道都值得串着刷。比如环形链表I后面跟着环形链表II再往后还有相交链表、反转链表、回文链表、合并两个有序链表等。如果你时间有限我建议按“遍历基础 - 双指针进阶 - 递归/迭代反转 - 综合操作”的顺序去练。环形链表I恰好是双指针链表题的起点先把这道题真正弄懂后面的路会顺很多。最后再分享一个小习惯刷题时我会单独建一个markdown文件专门记录每道题的最优解思路、复杂度分析和踩过的坑。环形链表这道题下我写了“快慢指针之间相对速度为1所以相遇是必然的不是碰运气”后来每次看到这句话都能提醒自己像链表这种结构有限的数据结构很多看似玄学的技巧背后其实都是确定性的数学关系。把这种确定性吃透才是刷题最大的收获。