【数据结构】快慢指针探秘理解链表与数组中的环结构1. 一次死循环引发的思考快慢指针到底解决了什么如果你写过链表的遍历代码大概率遇到过这样的场景在牛客网或者 LeetCode 上做题本地跑得好好的一提交就报“Time Limit Exceeded”。你第一反应是算法复杂度太高但仔细一看代码明明只有一层循环。再一排查发现问题出在测试用例构造了一个环形链表——你的遍历指针在环里转圈永远走不到空指针。这种情况我至少碰到过三次每次都要花好一阵子才能反应过来原来不是复杂度的问题而是链表里藏着一个“环”。链表中的环结构说直白点就是某个节点的 next 指针没有指向空而是指向了它自己或者它前面的某个节点形成了一条走不出去的循环路径。这种结构在实际业务中不常见但在面试题和竞赛题里几乎是必考内容。而处理这类问题最经典、最优雅的手段就是快慢指针也叫 Floyd 判圈算法。很多人第一次听到“快慢指针”时会觉得它玄乎其实它的原理特别朴素一个指针每次走一步另一个指针每次走两步两个人同时从链表头出发。如果链表中存在环那么走得快的那个指针最终一定会“套圈”追上走得慢的那个指针。如果链表中不存在环走得快的指针会先一步到达链表末尾的空指针循环终止。这篇文章我从快慢指针的数学原理讲起然后分别用链表和数组两个场景来做完整的手写实现再聊一些快慢指针的变形应用最后把我踩过的坑一并列出来。无论你是正在准备算法面试的应届生还是工作中偶尔需要处理链表、数组问题的工程师这篇文章都能让你彻底吃透这套思路。2. 为什么快指针一定追得上慢指针判圈算法的数学根基2.1 先建立直觉操场套圈如果你在跑步你大概体会过被快的人套圈的经历——你俩在环形跑道上跑快的人从后面追上来超过了你一圈。快慢指针检测环的逻辑跟这个一模一样慢指针就是前面那个跑步的人快指针就是后面那个追求者。链表中的环就是一座环形跑道链表头到环入口的那段路就是赛道外的入场通道。这里有个关键点如果链表中没有环两条指针一直沿着直线走快的先到终点一切结束。如果有环两条指针一旦进入环就永远在环里转悠。这时候快指针每次比慢指针多走一步等价于它在不断接近慢指针——每走一轮两人在环上的“差距”就缩减一步差距缩减到 0 的那一刻就是它们相遇的那一刻。注意快指针每次走两步、慢指针每次走一步这个“步长差为 1”的设计是有讲究的。稍后我会专门在“步长选择”小节里展开讲这里先记住结论。2.2 环内距离消减的完整推导我们把链表抽象成两个部分头节点到环入口的距离记为 a环本身的周长记为 L。假设慢指针入环时快指针已经在环里走了若干步了。由于快指针的速度是慢指针的两倍慢指针入环的那一刻快指针在环内已经建立起了一段“领先距离”。这里要注意环是一个圆形结构所以在快指针看来它要追上慢指针所需追赶的距离并不是简单的领先距离而是“环周长减去领先距离再取相对值”。换句话说快指针在环内追赶慢指针是沿着环的方向每走一轮它和慢指针之间的距离减少 1因为快走 2 步慢走 1 步相对距离减 1。我们设慢指针入环后快指针距离追上它还需要追赶 k 步。由于每轮追赶差距减小 1经过 k 轮后两个指针必然相遇。因为 k 是一个有限值而且最大不会超过环周长 L所以快指针一定能在有限步内追上慢指针而不是永远差一步。这里有一个容易被忽略的细节为什么快的不会跳过慢的比如快指针到达慢指针所在位置的下一个节点然后再次错过答案在于我们取的是“离散的节点”而不是“连续的线段”。两个指针都落在节点上快指针每次走两步慢指针每次走一步在步长差为 1 的条件下快指针会精确地从慢指针的当前位置“后一个节点”推进到“前一个节点”不会出现跨过慢指针而不相遇的情况。步长差为 2 或更大的时候才可能出现跳过的问题这也是为什么经典实现里强调快指针走两步、慢指针走一步的原因之一。2.3 时间复杂度和空间复杂度的账快慢指针最吸引人的地方是它的开销极低。时间复杂度是 O(n)因为慢指针最多走完从链表头到相遇点的全部路程——头节点到环入口的距离 a加上环内一圈的距离 L加上入环后的追赶距离这些加起来是线性量级不会超过节点数的常数倍。空间复杂度是 O(1)因为我们只额外创建了两个指针变量不论链表多长额外内存都是恒定的。对比一下使用哈希表的方案哈希表需要记录每个访问过的节点空间复杂度是 O(n)。换句话说快慢指针是用更少的空间换来了同样的时间在面试中如果你能写出快慢指针版本面试官通常会更满意因为它体现的不仅是代码能力更是对问题本质的理解。3. 链表环检测从判环到找环入口的手写实现3.1 单链表的自建数据结构我们先用经典的 C 语言风格定义一个单链表节点结构方便后面写代码时思路清晰。声明一下下面的代码我用 Python 写因为 Python 写起来最短、最容易读但思想跟 C 或 Java 完全一样。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next有了这个节点结构我们可以手动构造带环链表来测试。假设链表节点依次是 3 - 2 - 0 - -4然后 -4 的 next 指向第 2 个节点即 0 所在的位置这就构成了一个典型的带环链表环入口是值为 0 的那个节点。# 构造 3 - 2 - 0 - -4且 -4 指向 0 node1 ListNode(3) node2 ListNode(2) node3 ListNode(0) node4 ListNode(-4) node1.next node2 node2.next node3 node3.next node4 node4.next node3 # 成环3.2 判环函数最简单的 hasCycle判环函数只需要回答一个问题这个链表里有没有环有就返回 True没有就返回 False。def has_cycle(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这里我让快指针先走了一步初始位置是 head.next这样 while 循环里的条件判断更自然。当然你也可以让快慢指针都从 head 出发只是需要先判断 head.next 是否存在两种写法本质上没有区别。需要注意一个边界如果链表只有一个节点而且这个节点的 next 指向它自己那就是自环结构。上述函数中head 不为空head.next 也不为空因为它指向自己fast 初始化为 head.next即它自己slow 也是 head初始时两者相等函数直接返回 True。这个行为是正确的。3.3 找到环入口为什么相遇点不是入口很多初学者到这里会犯一个想当然的错误以为快慢指针相遇的地方就是环的入口。实际上两个指针只能在环内相遇而环入口是从链表外进入环的那个节点两者往往不是同一个节点。要找到环的人口需要用到一个小推导。假设a 链表头到环入口的距离b 环入口到相遇点的距离c 相遇点继续走到环入口的距离那么环的周长 L b c。当快慢指针相遇时慢指针一共走了 a b 步快指针一共走了 a b k * L 步其中 k 表示快指针已经在环里走了 k 整圈。因为快指针速度是慢指针的两倍快指针的总步数是慢指针总步数的 2 倍2(a b) a b k * L a b k * L a k * L - b a (k - 1) * L L - b (k - 1) * L c这个式子的意思是从链表头走到环入口的距离 a等于从相遇点继续走 c 步到达环入口然后可能再绕若干整圈 (k-1) 圈。换句话说如果我们把一个指针放在链表头另一个放在相遇点两个指针同时以每次一步的速度前进它们一定会在环入口处相遇——因为第一个指针走了 a 步到达入口第二个指针走了 (k-1)*L c 步也到达入口两者在入口处会师。这个结论非常实用。判断有没有环只需要快慢指针但要确定环入口就需要先找到相遇点然后再做一轮同步移动。def detect_cycle_entry(head): if not head or not head.next: return None 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 # 第二阶段一个从头开始一个从相遇点开始 slow head while slow ! fast: slow slow.next fast fast.next return slow提示第二阶段的两个指针每一次都只走一步。这个设计的数学依据就是上面的推导不要随意改成其他步长。3.4 编码细节与边界情况写链表环检测的代码最常见的错误就是把空指针访问了。比如 while 循环里直接写 fast.next.next如果 fast.next 本身是空那程序直接抛异常。所以每一轮 while 之前都要检查 fast 和 fast.next 是否为空。这是一道非常基础的健壮性考点很多代码虽然能过测试但边界一多就崩问题就出在这里。4. 数组里的隐藏链表用快慢指针找重复数4.1 把数组看成 i - nums[i] 的映射链表的环结构很好理解但数组里怎么会有环呢我第一次遇到这个问题时也愣了一下。其实只要做一个巧妙的映射把数组的每一个下标看成一个节点下标 i 的“next”指向 nums[i]这样整个数组就变成了一张有向图。比如数组 [1, 3, 4, 2, 2]它的映射关系是0 - 11 - 32 - 43 - 24 - 2按照这个规则走从 0 出发去 1再去 3再去 2再去 4再去 2再 4再 2……你会发现陷入了一个 2 - 4 - 2 的循环。这里的重复数字就是 2而它恰好是环的入口下标对应的值。这其实是 LeetCode 287 题“寻找重复数”的核心思路。题目要求数组长度为 n1数字范围在 1 到 n 之间必然有一个数字重复。由于数字不会超过 n我们用 nums[i] 作为下一个下标时永远不会越界。也就是说这个结构成一个有效的“隐式链表”。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几行代码就搞定了。这里有个很重要的细节第二阶段的 slow 初始化为 0而不是 nums[0]原因是我们要断开车头的隐式链表「寻找环入口」等价于「寻找重复数字」而重复数字就是环入口下标对应的值。让 slow 从下标 0 出发fast 停留在相遇点二者同步走最终会在环入口相遇返回值正是重复的那个数字。4.3 数组版本和链表版本的区别数组版本的快慢指针有一处容易坑到人不能像链表那样先判断指针是否为空因为数组下标不会为空。但正因如此如果你写错下标程序不会立刻崩溃而是会陷入死循环或者返回错误的结果。因此在实现时最好先用纸笔画一下映射关系搞清楚每条边指向哪里。另外数组版判圈的输入条件非常严格——数字必须在 1 到 n 之间。如果数组里有 0那么 0 的 next 还是它自己环就直接变成了自环重复数字的结论就会被破坏。所以这类题一般都会在题目说明里限定数字范围使用前务必确认题目条件。5. 快慢指针的变形应用中间节点、循环数组和其他场景5.1 寻找链表的中间节点快慢指针不仅能判环还能在不使用额外数组的情况下一趟找到链表的中间节点。思路很简单快指针每次走两步慢指针每次走一步。当快指针到达链表末尾时慢指针恰好走到链表中间。def find_middle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next return slow这里是单指针遍历做不到的一个指针走到头你得记录访问过的所有节点要么再遍历一半。快慢指针把「找中点」这个看似需要两次遍历或者 O(n) 空间的问题压缩到了 O(1) 空间一趟完成。实际应用里链表排序用到的归并排序分割链表就是靠这个思路找到中间节点的。5.2 判断循环数组还有一种题目给一个数组每个元素表示从当前位置跳跃的步数可能是正数也可能是负数问数组中是否存在一个循环。这种问题的本质就是快慢指针在有向图里找环的变种。你从某个下标出发按规则跳跃用快指针一次跳两步、慢指针一次跳一步如果相遇说明进入了循环。这道题比找重复数复杂一点因为跳跃规则可能涉及负数和取模而且循环方向必须一致。但核心骨架没有变把数组看成一张图用快慢指针判断有没有循环路径。所以只要把链表的判环思路吃透这类题的本质上都是一样的。5.3 其他值得关注的变形判断两个链表是否相交一种解法是把一个链表的尾接到另一个链表的头然后用快慢指针判环。不过这种解法会修改原链表手动实现时记得复原。求环的长度快慢指针相遇后让其中一个指针不动另一个继续每次走一步再次相遇时走过的步数就是环的长度。循环链表的约瑟夫问题在约瑟夫问题中循环链表删除节点的场景也需要判断链表有没有头结点等边界快慢指针的思路可以帮助快速定位目标节点。这些变形的共同点都是把“抽象结构中的循环路径”转化为“快慢指针的追赶问题”。6. 最容易踩的坑从步长选择到边界条件6.1 快指针步长为什么必须是 2这个问题我见过很多人问。为什么快指针不能一次走 3 步、4 步从数学上说只要快指针比慢指针快理论上最终都能追上。但如果步长差大于 1可能发生“跳过”现象快指针从慢指针的上一个节点直接跳到慢指针的下一个节点两者错过。当然在整数步长的前提下如果快慢指针继续在环内走快的还是会再次追上慢的只是需要额外的圈数效率变低代码的确定性也变差。步长差为 1 时快指针移动两步、慢指针移动一步每轮相对距离精确减 1不会跳过任何节点逻辑最干净。这也是面试标准答案默认快指针走两步的原因。如果你非要用快指针走三步在某些环长度和入口距离的组合下可能需要多绕好几圈才相遇虽然结论正确但推导起来复杂得多。注意快慢指针问题中步长差为 1 是最推荐的。初期练习时不要为了炫技改动步长先掌握标准解法再说。6.2 空链表和单节点自环空链表的问题很简单但单节点自环容易被忽视。判断一个链表是否有环如果链表只有一个节点且 next 指向自己很多初版代码会直接返回 False因为判断条件是 fast.next 是否为空而这个节点的 next 不为空判断会出错。所以写判环代码时优先检查 head 本身是否为空再讨论 next 的处理不要笼统地判断 next 是否存在。还有一类隐蔽情况链表头节点指向了链表中的某个节点但这个节点既不在链表的尾端也没有被引用计数管理。这种情况在 C 语言里会造成内存泄漏风险因为程序无法遍历到环内但不在主链上的节点。在算法题里我们不用管释放但在实际工程里这提醒我们链表操作时要特别小心指针指向。6.3 数组映射的越界风险数组版快慢指针最典型的错误是下标越界。比如数组是 [1, 2, 3, 4, 5]用 nums[nums[0]] 访问时如果 nums[0] 是 5那就越界了。所以题目条件里限定数字范围很重要在实际处理任意数组时需要对数组的边界做严格检查。另外数组里的 0 也要警惕。由于 0 的 next 是它自己如果题目允许值为 0快慢指针的判环就会碰上自环陷阱。所以看到数组版快慢指针题我建议你先看一下题目对数值范围的规定没有规定就先做一个预处理把不满足条件的值提前排除。6.4 一个让我印象深刻的翻车现场我之前在写找重复数的题时第二阶段直接写成了 slow nums[0]结果跑出来答案不对。后来仔细对了一遍推导才发现第二阶段必须从下标 0 出发而不是从 nums[0] 出发。因为第一阶段结束时slow 指向的是某个具体值这个值同时也是一个下标——这个下标恰好是环内的一个位置。而我们要找的重复数字是环入口下标对应的值所以第二阶段要让一个指针从链表头下标 0走另一个从相遇点环内位置走二者都以每次一步的速度前进。把 slow 初始化为 nums[0]等于让指针从链表头的下一个节点出发结果自然偏了。这种错误光靠调试很难发现因为结果不一定报错只是返回不正确的数字。所以我后来养成了习惯凡是快慢指针找环入口的问题一定要先在纸上画一次映射图把每个下标对应的 next 列出来走一遍流程确认第二阶段的初始位置再写代码。6.5 一个小技巧用“哨兵节点”降低复杂度在链表操作里哨兵节点dummy head是一个常用的技巧它能让代码在头部节点可能被删除或修改时避免大量分支判断。快慢指针的问题里哨兵节点不一定直接参与但如果你要在判环之外做链表反转或删除操作配合哨兵节点的代码会干净很多。想练习的话可以试着把环检测、找入口、删除入口节点三个操作连起来实现一个完整的“拆环”工具函数做完之后你会发现链表操作的基本功扎实了不少。后记练熟这套思路链表题基本就通了我在实际刷题的过程中快慢指针帮我也解决了很多非环问题。比如求链表倒数第 k 个节点用两个相距 k 的指针一前一后遍历本质上也是双指针思想的一种。可以说快慢指针不仅仅是“判环工具”而是一整套双指针思维方式的代表。如果让我给初学者一个练习路径我的建议是这个顺序先手写一遍链表判环再写查找环入口然后做一遍数组找重复数最后用快慢指针求链表中点和倒数第 k 个节点。这四个题做完你基本就能自如地运用快慢指针解决链表和数组中的路径类问题了。我个人习惯是把快慢指针的推导过程写在代码注释里这样下次回来看代码时能直接回忆起a b、kL、c这些变量的关系。真相就是理解了为什么相遇点能推导出入环口这套算法才算真正掌握否则换一个问法比如让你求环的长度你照样会卡住。