判断链表有没有环大概是数据结构与算法面试里出镜率最高的问题之一。我第一次遇到这题第一反应是拿哈希表记访问过的节点地址后来学了快慢指针才发现这题的正确姿势根本不是记地址而是让两个指针在链表上“赛跑”。快慢指针这个概念说穿了就一句话一个指针每次走一步另一个指针每次走两步如果链表里有环快指针最终会绕回来追上慢指针如果没环快指针会先撞到链表末尾。这个概念落到代码里不过十几行但背后的原理、边界情况和变体题目足够写出一篇很长的文章。今天这篇就把快慢指针从原理到应用完整拆一遍为什么是两步而不是三步、相遇点怎么算、怎么从“有环”进一步找环入口、数组里怎么玩同样的套路再加上我实际写这些代码时踩过的坑。适合准备面试、期末复习数据结构、写题时卡在环相关题目上的人以及想真正把链表搞明白的初学者。基础要求不高会一点 C 或者 Python 就能往下读。1. 快慢指针的本质把“判环”变成“追及问题”1.1 追及问题的生活类比你肯定在操场跑过步。一个跑得快、一个跑得慢同向出发如果跑道是直的快的人只会越跑越远两人再也不会有交集如果跑道是环形的快的人迟早会从后面追上来——因为慢的人一直在前面转圈快的人每一圈都在不断缩小两人的差距。链表的环检测就是这个物理场景的数字版把链表想象成跑道slow 每次移动一个节点fast 每次移动两个节点。链表有环相当于跑道是环形的fast 必然在某个时刻与 slow 相遇链表无环fast 会先到达“终点”NULL问题随之结束。这个类比不是随手拿来好玩的它直接揭示了快慢指针设计的第一原则要让两个指针“有可能相遇”两个指针的速度必须有差。都走一步两个人永远并排走在环里转再多圈也碰不上都走两步也一样。一快一慢才有“追赶”可言。理解了这个前提后面所有推导都顺理成章。1.2 为什么不用哈希表新手的直觉解法是用哈希表。每访问一个节点就把地址存进去如果某个地址在访问前已经出现过说明有环。这个解法没有错但代价是 O(n) 的额外空间。对于链表这样本身就不支持随机访问的数据结构面试官通常希望你能给出空间 O(1) 的方案快慢指针的最大优势恰恰就在这里只用了两个指针变量空间复杂度是常数级的。时间复杂度方面哈希表方案是 O(n)快慢指针也是 O(n)两者同阶但快慢指针省去了哈希计算的开销常数项更小。更重要的是快慢指针背后那一套“相遇点推导、环入口推导”的思想可以平滑迁移到找中间节点、判断回文链表、寻找数组重复数这一大片题目上而哈希表方案只是“判重”换一道题就基本废掉。数据结构学习里有个很常见的规律理解一个小的技巧远比背诵一道题的标准答案值钱。2. 核心原理相遇为什么必然发生2.1 从距离差看相遇设链表中“进入环之前”的直线段长度为 a从头节点到环入口不含入口节点环的长度为 b。slow 进入环后在环里走了 x 步时fast 已经在环里多走了多少这个问题看起来烦其实只要抓住一个核心事实每经过一个单位时间fast 比 slow 多走一步。为什么是“多一步”fast 一次两步、slow 一次一步一个单位时间内两人的行进距离之差恰好是 1。当 slow 刚好走到环入口时slow 已经走了 a 步fast 走了 2a 步。fast 在直线段上也消耗了 a 步所以它在环内比 slow 领先的“顺时针距离”就是 a 对 b 取模。这个领先距离并不重要重要的是进入环之后每走一个单位时间两人的距离差就稳定减少 1。最多 b 步之内fast 必然追上 slow。所以相遇必然发生而且只可能发生在环内不可能发生在环外的直线段上。用大白话再翻译一遍慢指针刚进环的那一刻快指针已经在环里领先了不等的一段距离但快指针是“追赶方”它每一步只能比慢指针多走一格于是差距一格一格地被磨掉直到归零。这就是环检测能够成立的底层逻辑。2.2 为什么必须是“两步”而不是“三步”“四步”常见的实现是 fast 走两步、slow 走一步。肯定会有人问fast 走三步、slow 走一步不行吗理论上也可能相遇但强烈不推荐。原因一效率下降。fast 每一步多跳一个节点但跳过的中间节点并不会因此被“省掉”时间复杂度依然是 O(n) 量级常数反而变大。环很长、直线段很长的时候fast 前期浪费的步数并不少。原因二存在“跳过”的风险。当 fast 的步长 k 与环长 b 之间存在公因数时fast 可能始终落在与 slow 交错的位置上追及变得不稳定。最极端的例子是环长 b2、fast 每次两步、slow 每次一步两人的落点可能永远错开。两步方案里因为2-11距离差是连续递减的任何环长下都不会出现“跳过”现象。这也是我反复跟别人强调的一个点不要为了“看起来更快”把步长改成 3 或 4。2-11这个简单的差从理论上保证了追赶的连续性这是两步方案最干净、最让人放心的原因。2.3 环入口一段被很多教材省略的推导判断有环只是第一步。真正刷题时题目往往会升级成“找到环的入口”。这时候要用到一个非常重要的结论从相遇点出发的指针继续走同时另取一个指针从头节点出发两者都每次走一步它们会在环入口处相遇。为什么设直线段长度 a环长 b两指针相遇时 slow 从环入口算起已经在环里走了 x 步。slow 总共走了 ax 步fast 走了 2(ax) 步。fast 比 slow 多走的距离 ax 一定是环长 b 的整数倍因为 fast 想追上 slow只能在环里多绕整数圈。于是ax ≡ 0 (mod b)也就是x ≡ -a (mod b)。这句话翻译成人话是从相遇点继续走到环入口所需的步数是 b-x从头节点出发走到环入口所需的步数是 a这两个距离在模 b 的意义下恰好相等。所以让一个指针从 h 头节点出发一个指针从相遇点出发保持同速它们会在环入口碰头。这个推导是找环入口算法的理论根基建议拿纸笔自己推一遍光看懂不算数。3. 实操链表环检测的完整实现与边界3.1 判断是否有环代码怎么写// C 语言判断单链表是否有环 int hasCycle(struct ListNode* head) { if (head NULL || head-next NULL) { return 0; } struct ListNode *slow head; struct ListNode *fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; if (slow fast) { return 1; } } return 0; }两个细节必须说清楚。第一循环条件是fast ! NULL fast-next ! NULL两个判断缺一不可。fast 每次走两步如果链表节点数是偶数最后一轮 fast 会停在最后一个节点上此时fast-next已经是 NULL如果循环里还去取fast-next-next就是直接解引用空指针程序当场崩溃。第二slow 和 fast 初始都指向 head而不是 fast 指向 head-next。两种写法都能判环但都指向 head 时逻辑最统一代码里少一层特殊判断。Python 版本同样直接def has_cycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False判断部分基本就是模板重点在于后续的入口和环长计算。3.2 找环入口第二次循环是关键基于 2.3 的推导找入口的代码就是在判环的基础上相遇之后把一个指针拉回头节点然后两个指针同速前进struct ListNode* detectCycle(struct ListNode* head) { struct ListNode *slow head, *fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; if (slow fast) { struct ListNode *p head; while (p ! slow) { p p-next; slow slow-next; } return p; } } return NULL; }这里有一个特别容易踩的坑有人以为相遇点就是环入口直接把 slow 返回这是完全错误的。相遇点只是 slow 和 fast 第一次碰头的位置通常不在环入口。只有经过第二次循环让新指针从头节点走 a 步、旧指针从相遇点走 b-x 步两者在环入口会合才能得到正确答案。3.3 环长度的计算环长度有三种求法。第一种在相遇点停下让一个指针继续绕环走数回到相遇点经过的节点数得到环长 b。第二种从环入口开始绕一圈计数。第三种用数学公式从 slow 的步数推算但代码实现最容易出错。实际写代码时最推荐第一种简单直接// 在确认有环且已知 meet 节点后 struct ListNode *p meet; int cycle_len 0; do { p p-next; cycle_len; } while (p ! meet);这段代码的边界情况是环长为 1 的链表也就是某个节点的 next 指向它自己。do-while 至少执行一次得到长度为 1结果正确如果换成 while 循环先判断再计数就会漏数一次得到 0。这种小细节最容易在实验报告和期末考题里翻车。3.4 边界条件清单环相关链表题的边界条件高度集中建议直接记下这张清单场景正确行为常见错误空链表 head NULL无环返回 NULL/0解引用空指针单节点自环有环入口就是头节点循环条件写错根本进不去循环单节点无环无环把 head-next 当 fast 起点后误判无环但链表很长fast 先到末尾正常退出只判断 fast漏掉 fast-next崩溃整条链表成环a0入口就是头节点忽略 a0 的情况找错入口直线段很长、环很小一定相遇时间略长误以为死循环提前退出4. 数组里的“环”把索引当成指针4.1 数组怎么会有环链表有环容易理解因为节点有 next 指针。数组没有指针怎么谈环关键在于一个建模技巧把数组当成“静态链表”——nums[i]的值表示下一个要访问的下标。比如nums [1, 3, 4, 2, 2]从下标 0 出发nums[0]1跳到下标 1nums[1]3跳到下标 3nums[3]2跳到下标 2nums[2]4跳到下标 4nums[4]2又跳回下标 2这就形成了一个环。数组里的环本质是“索引跳跃”产生的循环依赖。这个建模最经典的用处是 LeetCode 287“寻找重复数”。给定一个包含 n1 个整数的数组每个整数都在 1 到 n 之间其中至少有一个重复数要求不修改数组、只用 O(1) 额外空间找出这个重复数。排序不行哈希表也不行正解就是把数组当作链表下标 0 作为虚拟头节点nums[i]作为 next 指针用快慢指针找环入口环入口处的值就是重复数。这个解法被称为“数组里的链表环检测”几乎是快慢指针在数组上最具代表性的应用。4.2 数组版快慢指针的代码def find_duplicate(nums): slow nums[0] fast nums[nums[0]] while slow ! fast: slow nums[slow] fast nums[nums[fast]] # 相遇后从头找入口 slow 0 while slow ! fast: slow nums[slow] fast nums[fast] return slow为什么环入口的值就是重复数因为在跳转图里多个不同的下标指向同一个值等价于“多个入边指向同一个节点”这正是环入口的特征。快慢指针在数组上不直接比较节点地址而是比较下标所指向的值这是与链表版最大的区别也是最容易犯迷糊的地方。4.3 数组环场景下最容易翻车的点数组版有自己独特的坑。第一越界风险。链表里 fast 遇到 NULL 就停下来数组没有天然的 NULL必须依靠题目保证“值都在合法下标范围内”或“必然存在重复数”的前提来兜底否则nums[fast]可能访问到不存在的下标直接异常。第二初始化方式不能照搬链表版。链表版 slowfasthead数组版一般写 slownums[0]、fastnums[nums[0]]因为下标 0 相当于虚拟入口从它“后面”开始走才能避免循环条件失效。第三入口扫描时slow 要从 0 开始而不是从相遇点开始这个细节写错整道题的答案都会错。5. 常见问题与排查技巧实录5.1 死循环焦虑无环链表会死循环吗很多初学者写快慢指针时总担心“万一有环但没相遇卡死怎么办”。结论很明确只要代码逻辑正确无环链表绝不会死循环因为 fast 每轮至少前进两步最终必然碰到 NULLwhile 条件会正常退出有环链表则必然相遇。真正需要担心的是 while 条件漏写了一半比如只写while (fast ! NULL)而不检查fast-next ! NULL当链表节点数为偶数时最后一轮会试图访问fast-next-next而此刻fast-next已经是 NULL程序直接崩溃。我调试过不少次这类问题表现是时好时坏非常迷惑人其实根因就是那个被漏掉的判断。5.2 步长改成 3 的连锁问题有人为了让快指针更快把 fast 改成每次走三步。表面看没毛病但除了 2.2 节说的理论缺陷还带来一个现实麻烦循环里需要依次检查fast、fast-next、fast-next-next是否为空条件拉长可读性急剧下降而且依然无法保证必然相遇。我的建议是没有特殊原因就固定走两步。这是一个被大量题目检验过的稳定方案算法题里“稳定”比“看似更优”重要得多。5.3 排查清单速查表症状可能原因排查方法程序崩溃/段错误未判断 fast-next 是否为空检查 while 条件补全两个判断明明有环却说无环slow 与 fast 步长相同确认 fast 每次比 slow 多走一步找入口返回了错误节点直接把相遇点当入口返回确认执行了从头节点同速再走的第二次循环环长度多算或少算 1while/do-while 用错用环长为 1 的链表手推一遍数组版下标越界没有校验值的取值范围读题确认存在重复数等约束保证下标合法长时间不结束链表无环但 fast 没被正确推进检查 slow 或 fast 是否忘了前进5.4 调试技巧先把图画出来环位置一错代码很难靠肉眼调出来。我的习惯是先拿纸笔画图把链表画成节点方块加箭头标出 head、slow、fast 当前所在的位置手动模拟三五步看指针是不是按预期移动。这个办法听起来原始但对理解相遇推导和入口推导极其有效。带新人时我也常这么说能在纸上把 slow 和 fast 的轨迹画对代码基本就不会错。6. 从一道题到一片题快慢指针的扩展应用6.1 找链表中间节点快慢指针最顺手的扩展是找链表中间节点。slow 走一步、fast 走两步fast 到末尾时 slow 正好在中间。链表长度是奇数时slow 停在正中间长度是偶数时slow 停在偏右一个节点具体看题目要求。这个技巧不用额外空间不用先数长度再重新走一遍一次遍历就能定位。6.2 判断回文链表判断一个链表是否为回文教科书解法是先用快慢指针找到中间节点再把后半段链表反转然后从两头逐个比较最后视情况把后半段再反转回来恢复原状。三步都是 O(n) 时间、O(1) 空间比“转成数组再判断”漂亮得多。这道题把快慢指针和链表反转两个基本功合在一起考面试里出现频率很高。6.3 找倒数第 k 个节点另一个常见应用是“找链表倒数第 k 个节点”。不用快慢指针的笨办法是先遍历一遍数出链表长度再从头走 length-k 步用快慢指针的话让 fast 先往前走 k 步然后 slow 和 fast 同速前进fast 到末尾时 slow 正好停在倒数第 k 个节点。这个思路本质上和环检测同源用“距离差”定位而不是用“重新数数”。6.4 个人实操体会以我刷题和带算法的经验快慢指针最容易“看懂了原理但写不对代码”的地方有三个一是 while 条件的完整性二是找入口时第二次循环的起点三是数组版初始化时不能照搬链表版。把这三个点刻进脑子里环检测相关的题目基本就是模板题。另外如果要应付考试建议至少手写三遍第一遍照抄参考代码第二遍合上代码自己写第三遍给自己完整讲一遍推导过程。数据结构期末复习和考研 408 的链表算法题经常以环检测、找中间节点、单链表基本操作的形式出现能流利写出这几段代码比看多少遍网课都顶用。