企业官网建设流程全解析

【数据结构】快慢指针探秘：理解链表与数组中的环结构

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, val=0, next=None): 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 -> 1
• 1 -> 3
• 2 -> 4
• 3 -> 2
• 4 -> 2

按照这个规则走：从 0 出发，去 1，再去 3，再去 2，再去 4，再去 2，再 4，再 2……你会发现陷入了一个 2 -> 4 -> 2 的循环。这里的重复数字就是 2，而它恰好是环的入口下标对应的值。

这其实是 LeetCode 287 题“寻找重复数”的核心思路。题目要求数组长度为 n+1，数字范围在 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这些变量的关系。真相就是：理解了为什么相遇点能推导出入环口，这套算法才算真正掌握，否则换一个问法，比如让你求环的长度，你照样会卡住。