快慢指针详解：从链表判环到数组找重复数

刷链表题刷到一定数量之后，你会发现有不少题目都在围着“遍历”打转——找中点、找倒数第几个、判断有没有环、判断是不是回文。这些题表面长得不一样，解法却共享同一个套路：让两个指针以不同速度往后走。这个套路在数据结构里叫快慢指针，也有人叫龟兔赛跑算法。我最早是在《数据结构》课程里接触这个概念，后来刷 LeetCode 时发现它是链表题的隐藏主角，甚至还能反杀到数组里解决找重复数这类问题。

这篇文章就把快慢指针讲透。内容按实战逻辑展开：先解释两个指针为什么能“一个追一个”，再逐个拆环形链表、入环点、链表中点、倒数第 k 个、回文链表这些高频场景，每个场景都给出可复现代码和边界分析，最后分享我实际调试中踩过的坑。无论你是正在准备考研 408 数据结构，还是刷算法题找工作，或者只是想补一补基本功，这篇都能让你从“听说过快慢指针”变成“能用快慢指针解题”。

1. 快慢指针：两个指针的“速度差”能做什么

1.1 先理解最基本的直觉

快慢指针的思想一句话就能说完：在一条链表上同时派出两个指针，一个每次走一步，一个每次走两步，利用速度差来感知链表的结构特征。

这句话听起来平淡，但背后藏着一个关键的数学模型——相对速度。

想象两个人在圆形操场上跑步，一个人慢跑，一个人快跑。只要跑得足够久，快的人一定会从慢的人身后追上来，哪怕操场是弯的。这个追上的过程不需要知道操场具体有多长，也不需要知道两个人起点相差多远，只要速度不同、轨道闭合，相遇就是必然。

链表里的“环”就是这个闭合操场。快指针走两步、慢指针走一步，相对速度是每轮追近一个节点。只要链表存在环，两个指针早晚会相遇。如果在链表尾部的 null 处快指针先撞墙，说明没有环。

这个直觉看起来简单，却是整个快慢指针体系的源头。判断是否有环、找环入口、求链表中点，全都是这个直觉的不同变形。

1.2 为什么快指针每次走两步，而不是三步、四步

有人会问：快指针想追上慢指针，走快点不是更省时间吗？真实场景中，走三步、四步也能判断有环，为什么主流的实现一致选择“每次两步”？

答案与“环的长度”和“相对速度”有关。如果快指针每次比慢指针多走一个节点，那相对速度就是1。两个指针之间的距离差最大也就是环的长度 C。所以，最多经过 C 轮就一定追上。复杂度可控，逻辑简单。

相对速度一旦超过 1，分析就会多出很多麻烦。比如快指针一次走三步，相对速度是 2，那么当初始距离差不是 2 的倍数时，指针可能会擦肩而过，导致需要多判断一圈甚至提前落到 null。最极端的情况是在短环里，快指针还没追上慢指针，自己已经一步跳过了唯一出口，直接从环上“跳”到了链表尾。虽然这种情况通常可以通过边界条件规避，但实现起来细节更多，收益却几乎没有。

还有一个更微妙的问题：速度差太大时，快指针可能在一次移动中“跨过”慢指针所在节点。在链表这种线性结构里，跨过意味着两者不会在这一轮相遇，要多跑几轮才能碰上。虽然不影响最终结论，但推导和分析就绕了远路。

所以，每次两步是工程上的平衡点：保证相遇必然性的同时，把复杂度控制在 O(n)。

1.3 时间复杂度与空间复杂度

所有用快慢指针解决的链表问题，都在 O(n) 时间内完成，额外空间 O(1)——这恰恰是它最大的价值。

拿“判断链表是否有环”来说，主流替代方案是哈希表：遍历链表时把每个节点地址存进集合，如果碰到已经存在的地址，说明有环。哈希表方案在时间上是 O(n)，但空间是 O(n)。链表很长时，哈希表占用可能达到几百兆，而快慢指针方案只需要两个指针变量，内存开销是常量级。

在面试和考试场景里，空间复杂度的差别往往是决定性因素。题目如果加上“只能使用 O(1) 额外空间”的约束，哈希表方案直接出局。这也就是为什么快慢指针在《数据结构》教材和面试题里地位极高。

2. 环形链表与入环点：快慢指针的名场面

2.1 判断链表是否有环

LeetCode 141 是快慢指针的入门题：给定一个链表的头节点，判断链表中是否有环。

完整思路是：设置 slow 和 fast 两个指针，初始都指向 head。循环条件是 fast 不为空且 fast.next 不为空。每轮循环 slow 走一步、fast 走两步。如果在循环过程中 slow == fast，说明链表有环；如果循环正常终止，说明链表无环。

有人第一次接触时会有一个困惑：slow 会不会永远等不到 fast？不会。因为 fast 总比 slow 快，fast 闯入环内之后，会不断缩短两者之间的距离。每次缩短一个节点，最多绕环一整圈就能追上。这个“追上”的过程恰好证明了环的存在。

C 语言实现很经典：

bool hasCycle(struct ListNode *head) { if (head == NULL || head->next == NULL) { return false; } struct ListNode *slow = head; struct ListNode *fast = head->next; while (slow != fast) { if (fast == NULL || fast->next == NULL) { return false; } slow = slow->next; fast = fast->next->next; } return true; }

这里有个容易被忽略的细节：上面的写法让 fast 初始指向 head->next，而不是 head。这样做的目的是让循环条件变成 slow != fast，避免初始相同导致循环根本不进入。很多版本的教材会写成 fast 初始也指向 head，然后用 do-while 风格保证先跑一轮再比较，两种写法都可以，但初学者容易把两者混在一起。

我自己的习惯是慢指针每轮先走一步、快指针每轮先走两步，然后判断是否相等，循环条件用 while (fast && fast->next) 来控制，更直观：

bool hasCycle(struct ListNode *head) { struct ListNode *slow = head; struct ListNode *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { return true; } } return false; }

两种写法结果一样，但第二种的退出条件更清晰：快指针走到空指针，说明链表有尽头，必然没有环。

Python 版本更贴近刷题场景：

def hasCycle(head): slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: return True return False

2.2 找入环点：经典距离推导

判断有环只是第一步。很多题目更进一步：不仅要判断有环，还要返回环的入口节点。这就是 LeetCode 142。

解法分两阶段。第一阶段用快慢指针找到第一次相遇点；第二阶段把 fast 放回头节点，改为两个指针都走一步，第二次相遇的位置就是环入口。

第一次听到这个解法的人都会一脸懵：为什么第二次相遇就是入口？这里必须把距离算一遍。

假设链表头到环入口的距离是 a，环入口到第一次相遇点的距离是 b（沿着前进方向），相遇点继续走到环入口的距离是 c。那么环的长度就是 b + c。

慢指针从链表头出发，到第一次相遇时一共走了 a + b。快指针速度是慢指针的两倍，所以快指针走了 2(a + b)。同时，快指针从链表头出发，绕了 n 圈环之后到达相遇点，也可以表示为 a + b + n(b + c)。

两个式子联立：

• 快指针路程 = 2(a + b)
• 快指针路程 = a + b + n(b + c)

所以：

2(a + b) = a + b + n(b + c) a + b = n(b + c) a = n(b + c) - b = (n - 1)(b + c) + c

当 n = 1 时，a = c。也就是说，从链表头走到环入口的距离，等于从第一次相遇点继续走到环入口的距离。所以第二阶段让一个指针从链表头出发、另一个指针从相遇点出发，都走一步，相遇之处必然就是环入口。

当 n > 1 时，结论是 a = (n - 1)(b + c) + c，形式上是先绕了 n-1 圈再走 c 的距离，而绕圈不会改变相对位置，所以两个指针仍然会在环入口碰上。

C 语言实现如下：

struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *slow = head; struct ListNode *fast = head; int hasCycle = 0; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { hasCycle = 1; break; } } if (!hasCycle) { return NULL; } fast = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; }

第二阶段没必要让 fast 和 slow 再分谁快谁慢，统一走一步就行。这个解法对面试官非常友好，因为你能证明“为什么相遇点走到底就是入环点”，而不是死记硬背结论。

2.3 环与链表的长度关系要怎么算

找入环点之外，偶尔还有题目要算链表总长度或环的长度。环的长度可以从第一次相遇点开始，继续走一圈回到相遇点，记录步数。链表总长度则是链表头到入环点的距离（a）加上环的长度。

这一块没有新的算法，核心还是在快慢指针的基础上补充一次遍历。不要小看这些变体，考研题和面试题经常把“判环”和“求长度”放在同一个答题流程里，考的是你是否真正理解了指针从哪儿出发、在哪儿停下。

3. 中间节点、倒数第k个与回文判断：快慢指针的日常用法

3.1 找链表的中间节点

路径：慢指针每次走一步，快指针每次走两步。当快指针走到链表末尾时，慢指针刚好停在中间位置。

LeetCode 876 就是原题。对偶数长度的链表，题目要求返回第二个中间节点。使用“fast 从 head 出发，每次走两步，slow 从 head 出发，每次走一步”的方式，当 fast 走到 null 时，slow 正好指向第二个中间节点。

代码非常简洁：

def middleNode(head): slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow

这里最值得讲的是“为什么停在中间”。链表长度为奇数 n 时，fast 走到最后一个节点，slow 走了 (n-1)/2 步，停在正中间；链表长度为偶数 n 时，fast 走到 null，slow 走了 n/2 步，停在靠右的中间节点。这个行为刚好满足题目要求，不需要额外判断长度奇偶。

如果题目要求偶数长度时返回靠左的中间节点，只需要 slow 初始指向 head，fast 初始指向 head->next，就能避开。

找中间节点之所以重要，不只是因为题目本身，而是因为它是一切“切开链表”操作的前置步骤。回文判断、链表排序、构建平衡二叉树，都会先用快慢指针找到中点。

3.2 寻找倒数第 k 个节点

倒数第 k 个节点不需要快慢速度差，但用的是同一种指针配合思想。

思路是：fast 先走 k 步，然后 slow 和 fast 一起走一步，直到 fast 走到 null。此时 slow 恰好指向倒数第 k 个节点。

这个做法本质上是让 slow 和 fast 之间保持长度为 k 的窗口。fast 先跑 k 步，确定了窗口右侧，然后窗口整体平移，直到右侧顶到链表尾。

代码：

def findFromEnd(head, k): slow = head fast = head for _ in range(k): if not fast: return None fast = fast.next while fast: slow = slow.next fast = fast.next return slow

边界条件是 k 大于链表长度。循环里 fast 提前碰到 null，直接返回 None。这也是比“先遍历一遍求总长度，再走 n-k 步”更优雅的做法，因为它只需要一次遍历。

我处理这类题的核心感受是，快慢指针本质上就是“窗口滑动”的链表版：你让两个指针保持固定距离，或者保持固定相对速度，信息自然浮出水面。

3.3 回文链表：快慢指针和反转的配合

回文链表（LeetCode 234）是快慢指针最典型的复合应用。判断一个链表是不是回文，第一反应是用栈或者数组存下来再比对，但那样空间复杂度是 O(n)。快慢指针方案只需要 O(1) 额外空间。

思路分三步：

1. 用快慢指针找到链表中间节点。
2. 从中间节点之后的部分反转链表。
3. 从头节点和反转后的头节点同时遍历，逐节点比较值。

完整 Python 实现：

def isPalindrome(head): if not head or not head.next: return True slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next prev = None curr = slow while curr: nxt = curr.next curr.next = prev prev = curr curr = nxt left = head right = prev while right: if left.val != right.val: return False left = left.next right = right.next return True

这个解法把快慢指针和链表反转结合到一起，是“基础算法组合拳”的典型。面试时能写出这个方案，比用栈存储再比较的方案加分不少，因为你的空间复杂度做到了最优。

值得提醒的是，判断回文前如果先找到中点是第二个中间节点，反转后半段之后，链表长度是偶数时两边完全对应，是奇数时右侧链表比左侧短一个节点，所以比较时只以 right 不为空作为循环条件，不会出现越界。

4. 边界条件、常见坑位与调试实录

4.1 空链表和单节点链表的处理

快慢指针代码的第一行几乎都是空指针检查。head 为空，或者 head.next 为空，很多题都可以直接返回。这个“直接返回”很容易被忽略，但遗漏之后代码会在 while 条件里访问空指针的 next，直接崩溃。

我见过最多的错误就是循环条件写得不够宽松。判断有环时，如果链表是单节点且自环，那 head.next == head，快指针走两步会回到自身，检测逻辑没问题。如果链表是单节点但没有环，快指针从 head->next 出发会立刻变成 NULL，必须在 while 条件里写 fast != NULL && fast->next != NULL，否则解引用空指针就是事故现场。

规则可以简单记：只要快指针要连续走两步，就必须保证 fast 和 fast.next 都不为空。这是快慢指针代码的第一条安全准则。

4.2 fast 初始位置的选择

判断有环的代码里，fast 初始可以指向 head，也可以指向 head->next。这个选择会改变循环结构：

• fast = head 时，初始 slow == fast，必须用 do-while 或者先移动后比较，否则循环不会进入。
• fast = head->next 时，初始 slow != fast，可以直接进入 while (slow != fast) 循环。

很多刷题新手把不同的初始条件抄混了，导致代码陷入死循环或者直接跳出不判断。

想避免这个问题，建议固定一种模板：fast 初始等于 head，循环用 while (fast && fast->next)，每轮先移动再比较。这个模板在判断有环、寻找入环点、找中间节点时都能复用，不容易记错。

4.3 相遇一定会发生，但慢指针不会在环里转圈

查看代码时，有人会追问：如果环很长，快指针追上慢指针要很久吗？其实不需要。前面推导过，相对速度是 1，所以追上所需的轮数不会超过环长。

更重要的结论是：慢指针在环里最多走不完一圈就会被追上。慢指针进环之前，快指针已经进环一段时间了，它可能正在环里某个位置等它。慢指针进环后每走一个节点，快指针逼近一步，两者距离减一。由于两者初始距离小于环长，慢指针走完一圈之前，快指针必然已经追上。

这个结论在找入环点阶段特别有用，因为它保证相遇点发生在慢指针第一次进入环后不久，数学推导里的 b 和 c 的关系也能保持稳定。

4.4 快慢指针 vs 哈希表：什么时候用哪种

快慢指针并不总是最优解。如果题目只要求判断是否存在环，而且不限制空间复杂度，哈希表在思路上更直接，代码也更不容易出错。

哈希表方案的流程：遍历链表，每到一个节点就把地址存进 set 或 map。如果发现当前节点已经存在，说明有环。这个方案的优势是天然支持“找到具体节点”——存的是完整指针，不是值。

快慢指针方案的唯一缺点是数学理解门槛略高，面试时需要现场推导。但它的空间复杂度碾压哈希表，面对大数据量链表时优势明显。

实际建议是：练习题必须快慢指针和哈希表两种都写一遍；面试时优先说快慢指针，因为能展示你掌握了 O(1) 空间的解法，同时还能讲解原理；笔试或者牛客网这种需要快速 AC 的场景，用你最熟练的那个。

4.5 调试快慢指针代码的一个实用方法

链表题的调试一直比数组题麻烦。节点地址在内存里不连续，没法一眼看出谁是谁。我的习惯是写一个辅助函数，把链表的节点值按顺序打印出来，如果怀疑有环或者循环异常，就在里加一个计数器，最多循环 1000 次强制退出，打印出 slow 和 fast 各自指向的值。

这个方法很多教程不会提，但排查死循环时特别好用。尤其是自己构造测试链表时用了带环的用例，如果不限制循环次数，程序会一直跑，你甚至分不清是代码逻辑错了还是确实在环里没出来。

5. 从链表到数组：快慢指针的进阶玩法

5.1 循环数组检测

快慢指针不仅能处理链表，还能处理数组。LeetCode 457 就是一道典型的“循环数组”题：数组每个元素表示下一步要移动的步数，正值向右走，负值向左走，问数组中是否存在一个满足条件的循环。

这类问题把数组下标看成一个虚拟链表节点，下标 i 通过 nums[i] 的值计算出下一个下标，也就是“下一步的指针”。于是数组就变成了一个有节点、有边的图遍历问题。快慢指针用在这条虚拟链表上，判断是否存在闭环。

因为数组下标是连续的，判断是否回到同一个下标就能确定环。这个题目比链表判环多一个限制条件：循环的方向必须全部相同，即不能一个节点向右、一个节点向左。所以实现时除了快慢指针，还要记录每一步的方向。

5.2 数组里的“找重复数”为什么能用龟兔赛跑

LeetCode 287 是另一道看上去和链表毫无关系的题目：给定一个包含 n+1 个整数的数组，每个整数在 1 到 n 之间，至少存在一个重复整数，找出这个重复数。要求不能修改数组，只能用 O(1) 空间。

解法居然还是快慢指针。思路是把数组值当作索引去访问，形成一张隐式链表：

• 从 index 0 出发，nums[0] 是下一个索引
• 从该索引出发，nums[nums[0]] 是再下一个索引
• 以此类推

因为有重复元素，必然有两个不同下标映射到同一个值，这张隐式链表里必然存在环。环的入口对应的值就是重复数。

这个过程和“找链表的入环点”如出一辙：第一阶段快慢指针相遇，第二阶段从起点和相遇点同时走，直到再次相遇，相遇处的索引就是重复元素。这个解法巧妙的地方在于把数组下标和值互相映射，构造出一个虚拟链表，而龟兔赛跑算法刚好用于这个虚拟链表。

5.3 进阶题的组合规律

观察这些进阶题可以发现一个模式：快慢指针本质上是一种图遍历算法，只不过作用在“线性但可能存在回环”的结构上。链表、循环数组、隐式映射图，这些结构都可以抽象成节点和边，快慢指针判断的核心就是“是否存在回环”。

掌握了这个抽象，看到貌似无关的题就不会慌。先问一句：这个结构能不能变成一张图？这张图是不是可能有环？如果都能，快慢指针就值得一试。

在我自己的刷题节奏里，快慢指针是少数几个我愿意反复回看的算法。它的第一眼看上去很绕，可一旦理解了相对速度、入环点距离推导，后面所有变体都能自然推导出来。比死记十道题模板有意义得多。

6. 配套练习与常见误区速查

6.1 练习顺序建议

单独讲一个算法不配几道练习题，等于白讲。我建议按下面顺序刷，由浅入深：

1. LeetCode 141 判断链表是否有环
2. LeetCode 876 链表的中间节点
3. LeetCode 142 寻找环形链表的入口节点
4. LeetCode 234 回文链表
5. LeetCode 287 寻找重复数
6. LeetCode 457 环形数组循环

前四题覆盖了链表场景的全部基础，第五题打破“只能用于链表”的思维定式，第六题把方向约束加进来，算是对快慢指针的完整练手。

6.2 高频误区一览

结合我自己被坑过的经验和看别人踩过的坑，这个算法有以下几个高频误区：

6.3 一套模板打天下

最后分享一个非常实用的个人经验：快慢指针题虽然看起来多变，核心模板就一套。判断环、找入口、找中点，本质上都是同一套移动逻辑。

def twoPointersTemplate(head): if not head or not head.next: return None slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next # 根据题目要求在这里做判断 return slow

其余代码都是在这个模板上做加减法：判断有环就检查 slow == fast；找中点就注意循环结束时 slow 的位置；找入口就把 fast 移回头节点再同步走。

这套模板写顺手之后，面试时碰到链表类题目，思路会被拉回这个框架，答题速度快很多。我个人在备考和面试阶段都是这么练的，建议你也直接在这个骨架上针对性改条件，别每次重新从零设计算法逻辑。