快慢指针判环可能是链表算法题里最经典又最容易被“背下来”的一道。背完解法的人不少但真正被面试官追问时卡住的人更多为什么快指针每次要走2步、慢指针每次走1步步长差改成2行不行改成3甚至改成5行不行这篇文章就把“步长差”这件事彻底拆开。你会看到一个反直觉的结论在离散链表上任意正整数的步长差最终都能让两个指针相遇但步长差等于1在可相遇位置的覆盖范围、环入口定位、时间复杂度稳定性三个维度上都是那个最省事、最稳妥的答案。后面我还会用JS把快慢指针思想的另一个常考形态——有序数组原地去重——一起讲透。1. 先厘清概念判环、环长与步长差的定义1.1 单链表判环问题的经典场景给定一个单链表判断链表中是否存在环。这是LeetCode 141题的场景也是面试中最高频的链表题之一。所谓“环”就是某个节点的next指针指回了它前面的某个节点导致从那里开始无限循环。更极端的情况是尾节点指向自身形成一个自环。经典快慢指针做法非常简单function hasCycle(head) { let slow head; let fast head; while (fast fast.next) { slow slow.next; fast fast.next.next; if (slow fast) { return true; } } return false; }每个指针每轮移动一次慢指针走1个节点快指针走2个节点。如果链表无环快指针会先一步到达null如果有环两个指针最终会陷入环内并相遇。这个算法的巧妙之处在于不用额外空间只靠两个指针的相对速度差就能检测出是否存在周期性结构。1.2 “步长差”和“速度比”不是一回事很多人讨论这个算法时把“速度比2:1”和“步长差为1”混着说真到推公式时会把自己绕晕。我在这篇文章里统一约定慢指针每轮移动1个节点。快指针每轮移动m个节点m是大于1的正整数。步长差d m - 1即每轮快指针比慢指针多走的节点数。经典配置是m 2也就是步长差d 1。为什么刻意区分这两个概念因为后文所有数学推导都建立在“每轮快指针比慢指针多走d步”这个相对位移上与m的绝对值关系不大。搞清楚这一点才能理解为什么“快指针每次走3步”并非完全不可行只是不如d 1好用。2. 追及问题的数学建模相遇条件的同余方程2.1 从相对位移推导出核心方程先定义链表的几何参数。设从链表头节点出发走到环入口需要a步非环部分长度环的周长为L。注意这里说的“步数”是节点的跳数头节点是第0个节点它到环入口的跳数就是a。慢指针从起点出发走了a步后第一次踏上环入口。此时快指针已经走了m * a步。因为前面a步消耗在非环区快指针在环内实际移动了m * a - a (m - 1) * a d * a也就是说快指针进入环后停在环内位置p (d * a) mod L处。这里“环内位置”指的是从环入口出发沿链表的next方向往前走k步到达的节点位置编号为0到L - 1。慢指针踏上环入口那一刻把它记为第0轮。慢指针在位置0快指针在位置p。接下来每经过一轮慢指针环内位置加1快指针环内位置加m d 1。经过x轮后慢指针位置x mod L快指针位置(p m * x) mod L即(d * a (d 1) * x) mod L两个指针相遇意味着两者的环内位置相同x ≡ d * a (d 1) * x (mod L)把含x的项移到同一边d * x ≡ -d * a (mod L)也就是d * (a x) ≡ 0 (mod L)这个式子就是整篇文章的核心。以后遇到任何快慢指针的变形题都可以直接套这个同余方程不必从头推。2.2 方程的解总是存在任意正整数步长差都能相遇看到这个方程第一反应可能是如果d和L不互质是不是可能永远不相遇不会。设g gcd(d, L)则方程两边可以约去d和L的最大公约数(d / g) * (a x) ≡ 0 (mod L / g)因为d / g与L / g互质所以上面这个同余方程等价于(a x) ≡ 0 (mod L / g)也就是说只要x满足“a x是L / g的整数倍”两个指针就相遇。这样的x一定存在。取x L / g - (a mod (L / g))再对结果取模就能得到最小非负整数解。这个结论很重要只要快指针比慢指针快d 1在离散的链表环上两个指针最终一定会在某个节点相遇。所以“快指针每次走3步慢指针走1步永远碰不上”的说法并不准确。它只有在某些特定实现有缺陷、或者把“相遇”理解成“在连续移动过程中擦肩而过也算”时才可能出现偏差。按每轮结束后位置来判断相遇是必然的。2.3 可相遇位置的范围由 gcd 划定虽然一定能相遇但“在哪些位置相遇”却受d和L的约束。从解的形式看a x必须是L / g的整数倍。所以x的通解是x -a k * (L / g), k 0, 1, 2, ...第一次相遇发生在k取到使x非负的那个值之后每隔L / g轮两个指针又会重逢一次。用大白话解释当g 1时快指针和慢指针只能在环上的一部分节点上相遇另一部分节点永远不可能是相遇点。比如L 8, d 2时g 2可相遇位置之间的间隔是L / g 4也就是说它们只能在所有编号模4同余的节点上碰头。只有g 1即d与L互质时相遇位置的间隔才是L理论上每个环内节点都可能成为相遇点。这正是步长差d 1的关键优势之一gcd(1, L)永远等于1无论环长是多少可相遇位置都不会受到任何限制。3. 步长差等于1的独特地位为什么工程上最终选它3.1 最坏轮数和总步数的量化对比既然任意步长差都能相遇为什么没有人写一个“快指针每次走3步、慢指针走1步”的判环版本效率问题是其中一个原因。相遇轮数的最小非负解满足x L / g - 1而快指针在环内每轮要移动m d 1步所以到相遇时快指针在环内移动的总步数为m * x把d从1开始逐个比较步长差 d快指针步长 mgcd(d, L) 的两种情况相遇轮数上限快指针环内总步数上限12恒为1L - 12L - 223g 1 或 2g1时 L-1g2时 L/2-1g1时 3L-3g2时 1.5L-334g 1 或 3g1时 L-1g3时 L/3-1g1时 4L-4g3时 约1.33L-4这个表说明什么问题当d和L恰好不互质时因为相遇轮数上限降到了L/g - 1总步数不一定差但当二者互质时d越大快指针总步数的上限就越高。最坏情况下d 1是快指针移动步数最少的选择。更关键的是链表遍历前并不知道L是多少所以无法预判gcd(d, L)的值。为了在所有环长下都有稳定的最坏情况表现d 1是唯一一个不依赖L就能保证“最坏只是2倍慢指针距离”的选择。3.2 位置覆盖无死角每个节点都可能成为相遇点假设你不仅要判环还要统计环上哪个位置是第一次相遇点或者用相遇点做进一步计算。当d 1时g 1方程退化为a x ≡ 0 (mod L)x在模L下有唯一解。随着a取不同值相遇点可以覆盖环上任意节点。这个“无死角”特性在做环入口推导时是不可或缺的。当d 2且环长L 8时可相遇位置被限制在编号模4相等的两个节点上。如果你用这样的相遇点去做后续定位就会得到错误结果。3.3 环入口定位公式强烈依赖步长差等于1这里直接给出结论LeetCode 142题的“找环入口”算法是在第一次相遇后把一个指针放回链表头另一个留在相遇点两个指针都以每轮1步的速度前进再次相遇的位置就是环入口。这个证明的核心一步要求第一次相遇时“慢指针的总步数恰好是环长的整数倍”也就是a x ≡ 0 (mod L)。当d 1时条件自然满足。当d 1时通解变成a x ≡ 0 (mod L/g)少了整整g倍的精度。后续推导全部失效二次相遇根本不会发生在环入口。这一点的详细推导放在第5节。4. 用具体链表模拟不同步长差的相遇过程4.1 构造一个可直接验证的示例链表为了让前面的公式落在地上我构造一个带环链表来模拟。链表结构如下节点1 - 节点2非环部分长度a 2节点2 - 节点3节点3是环入口节点3 - 节点4 - 节点5 - 节点6 - 节点7 - 节点8 - 节点3环长L 6环入口位置编号为0节点3位置1对应节点4位置2对应节点5以此类推。模拟走法很简单慢指针从节点1出发第2轮到达环入口节点3此时根据公式快指针在环内位置为(d * a) mod L (2d) mod 6。用前面的同余方程d * (a x) ≡ 0 (mod L)算出每种步长差下的相遇轮数x和相遇位置结果如下步长差 d快指针步长 m快指针入环初始位置相遇轮数 x相遇位置快指针总步数 m*(ax)1224412234119340008452111556444366700014注意第三行d 3时快指针入环初始位置就是0等于慢指针刚到环入口的位置所以x 0两者直接碰面。这不是特例当d * a是L的倍数时都会出现这种情况。还有一个值得注意的细节d 6时方程6 * (2 x) ≡ 0 (mod 6)对任意x恒成立所以x 0是最小解。不是“任何时刻都相遇”而是“在慢指针进入环的那一刻恰好相遇”之后两者因为步长差是环长的整数倍反而保持相对位置不变每轮都同步出现在同一个节点上。4.2 再试一组不同参数非环长度为1环长为8换一个结构a 1L 8环入口位置编号为0环内共有8个节点。慢指针走1步到达环入口快指针初始环内位置为d mod 8。模拟结果如下步长差 d快指针步长 m快指针入环初始位置相遇轮数 x相遇位置可相遇位置间隔121778232334343778454112565778676338787778“可相遇位置间隔”指的是解的通项中x的增量也就是L / g。当g 2时间隔为4当g 4时间隔为2。从这两组数据可以直观看到d 1时相遇轮数最糟糕需要走到环内位置的最后一个节点才碰上但它每次都能相遇而且相遇位置覆盖了环上所有可能的位置。d 2或d 4虽然有时相遇得更快但可相遇位置被限制在环上的部分节点后续计算容易受牵制。4.3 一个可以直接运行的验证脚本如果不想手动试验可以用下面这段JS脚本快速验证function meetTime(a, L, d) { let x 0; while ((d * (a x)) % L ! 0) { x; } return x; } for (let d 1; d 6; d) { console.log(d${d}, 相遇轮数${meetTime(2, 6, d)}); }这段脚本验证的是数学方程的解不是链表模拟。它可以帮助你理解“为什么不同步长差最终都会相遇”的结论而不必真的去构造链表对象来跑。5. 找环入口为什么非要在2:1的配置下做5.1 标准二次相遇算法的完整推导先说标准做法。第一次用2:1速度比找到相遇点后设相遇时慢指针从起点一共走了S步非环部分长度是a慢指针进入环后走了x步所以S a x因为步长差是1相遇时快指针比慢指针多走的步数等于慢指针总步数S。而从起点到相遇点快指针比慢指针正好多走了若干整圈因此存在正整数k使得S a x k * L也就是说a x是环长L的整数倍。现在看相遇点。慢指针在环内位置为x mod L。从这个位置继续沿链表的next方向走要回到环入口位置0需要的步数y满足x y ≡ 0 (mod L)所以y ≡ -x ≡ a (mod L)这句话翻译成人话就是从相遇点绕回环入口所需的距离和从头节点走到环入口的距离在模环长意义下相等。因此把一个新指针p放回链表头另一个指针q留在相遇点两者都以每轮1步的速度前进。当p走了a步到达环入口时q也恰好走了a步到达环入口。两者在环入口相遇。这就是“二次相遇找环入口”算法的证明。5.2 如果步长差不是1二次相遇会走到哪里假设第一次相遇使用了步长差d 1此时第一次相遇满足的条件变成a x ≡ 0 (mod L / g)其中g gcd(d, L)。从相遇点回到环入口所需的步数y依然满足x y ≡ 0 (mod L)。于是y ≡ -x (mod L)而新指针从头节点出发走a步到达环入口。我们来比较两个指针各自走完a步之后的位置新指针在环内位置是0环入口从相遇点出发的指针走完a步后位置是x a在环内的余数由第一次相遇条件可得a x ≡ 0 (mod L/g)所以这个余数只能保证是L/g的整数倍不保证是L的整数倍。当g 1时L/g严格小于L结果不一定是0。举一个具体反例。回到第4节的示例a 2, L 6, d 2。第一次相遇轮数x 1相遇位置是环内位置1节点4。用二次相遇算法新指针从起点走a 2步到环入口节点3另一个指针从位置1走2步到环内位置3节点6。两者并没有相遇差了整整半个环。所以结论很明白二次相遇找环入口的算法必须建立在d 1的第一次相遇基础上。如果用了其他步长差即使第一次能相遇也无法复用这个标准推导。5.3 工程建议判环就用2:1全程不要换速度既然d 1在数学上最优、在工程实现上最简单、在后续推导中最省事实际项目中根本没有理由使用其他步长差。有些面试者会问能不能先让快指针每次走3步等相遇后再改用2:1重新跑可以但等于多跑一遍没有任何收益。直接在第一次就使用2:1是理论、实践、代码可读性三个维度上的综合最优解。6. 快慢指针思想在JS有序数组去重中的落地6.1 从“环形追及”到“区间整理”快慢指针并不只属于链表判环。在有序数组原地去重问题中同样能看到它的身影这也是“js快慢指针有序数组原地去重”这个热搜词背后的高频面试题。LeetCode 26题的描述是给定一个有序数组原地删除重复元素使每个元素只出现一次返回删除后数组的新长度。要求不能使用额外数组空间必须原地修改。这个场景里的“快慢指针”不是靠步长差追及而是让两个指针以不同节奏推进快指针read负责扫描整个数组每轮固定前进1步保证不遗漏任何元素。慢指针write负责记录下一个不重复元素应该写入的位置。当快指针发现一个新元素时就把它写到write指向的位置然后write前进1步。这里的“速度差”不是每轮移动步数不同而是“触发前进的频率”不同。遇到连续重复元素时write原地等待遇到新元素时write才追赶一步。6.2 JS原地去重的核心代码与逐步解释先看完整实现function removeDuplicates(nums) { if (nums.length 0) return 0; let write 1; for (let read 1; read nums.length; read) { if (nums[read] ! nums[write - 1]) { nums[write] nums[read]; write; } } return write; }逐步解释数组有序所以重复元素必然相邻。write从1开始因为第一个元素天然保留在nums[0]不需要处理。read从1开始遍历。每次比较nums[read]和nums[write - 1]。nums[write - 1]是当前已经确认保留的最后一个不重复元素。如果两者不同说明nums[read]是新的不重复元素写入write位置然后write前进。如果相同说明还是重复元素write不动继续让read扫描。遍历结束后write的值就是数组中不重复元素的个数前write个位置就是去重后的结果。举例输入: [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] 过程: read1, 值0, 与 nums[0]0相同跳过 read2, 值1, 与 nums[0]0不同写入 nums[1]1write2 read3, 值1, 与 nums[1]1相同跳过 read4, 值1, 与 nums[1]1相同跳过 read5, 值2, 与 nums[1]1不同写入 nums[2]2write3 ... 输出: [0, 1, 2, 3, 4]返回5时间复杂度O(n)空间复杂度O(1)完全满足原地要求。6.3 去重场景与判环场景的“步长”类比判环和去重表面上差异很大但内在逻辑是一家人都是用一个指针作为“基准”另一个指针作为“探测器”利用指针之间的距离差记录状态从而避免创建额外数据结构。判环场景中两个指针的“步长”直接写死在移动逻辑里slow slow.nextfast fast.next.next。步长差决定了追及方程方程又决定了相遇位置的可能性。去重场景中快指针的“步长”固定为1它永远不会跳过任何一个元素慢指针的“步长”不是固定值而是在发现新元素时才移动1步。这个可变的“写入步长”正是快慢指针思想在非周期数据结构上的自然延伸。如果面试官问“为什么去重时快指针不能一次走2步”答案也很直接有序数组去重需要逐个判断相邻元素是否重复跳过任何一个元素都会导致错误结果。判环时可以大步跨越是因为环的周期结构允许相对位移累积去重时没有周期结构可以利用必须老老实实逐个检查。7. 动手实现时最常踩的坑和避坑建议7.1 循环条件写错导致的空指针判断链表是否有环时循环条件必须同时检查当前指针和下一个指针while (fast ! null fast.next ! null)不少初学者只写while (fast.next ! null)。当链表没有环且fast已经走到最后一个节点时fast.next是null可以退出循环但在那之前fast可能已经变成null再去访问fast.next就会直接抛空指针异常。正确的写法是先判断fast ! null再判断fast.next ! null顺序不能反。7.2 半途改变步长会让追及方程失效判环过程的每一次迭代都要保持快指针每轮走2步、慢指针每轮走1步。如果把循环体写成了下面这种混搭形式基本就废了while (fast fast.next) { slow slow.next; fast fast.next.next; // 后面又鬼使神差地写了一句 // fast fast.next; }步长一旦在中途改变前面所有轮次的相对位移记录都对不上了后续推导也要全部重来。快慢指针不是“以哪个速度都能跑”而是“一旦选定速度比就必须从头到尾保持一致”。7.3 入口定位时的对象复用问题第一次相遇后要把其中一个指针重新指向链表头。这里容易犯的错是直接新建一个变量从头开始却忘了保留相遇时另一个指针的位置。标准实现通常这样写function detectCycle(head) { let slow head; let fast head; while (fast fast.next) { slow slow.next; fast fast.next.next; if (slow fast) { let p head; while (p ! slow) { p p.next; slow slow.next; } return p; } } return null; }注意第二个while循环里p从头节点出发slow从相遇点出发两者每轮都走一步最后在环入口相遇。如果你不小心把slow又重新赋值为head那这个循环就永远不会退出。7.4 节点比较用引用而不是值JS中判断链表节点相等要用slow fast比较对象引用不能比较节点的val。不同节点可能拥有相同的值但它们在内存中的身份不同。判环的实质是判断“移动到了同一个节点对象”而不是“两个节点值相等”。7.5 不要忽略自环和空链表边界空链表head为null应该直接返回false或null。单节点无环head.next为nullwhile条件直接不满足安全退出。单节点自环head.next指向自身。此时slow和fast都从head出发第一轮迭代后slow变成head.nextfast变成head.next.next又都是head二者相遇返回有环。这个边界在代码里天然支持不用额外处理。经历了这次对步长差的彻底拆解我自己的一个体会是遇到这类“背下来容易、讲清楚难”的算法题最好的学习方法不是再多刷几道题而是把变量替换成符号亲手推一遍等式。只要把d * (a x) ≡ 0 (mod L)这个式子印在脑子里以后面试官再问“为什么快指针不能走3步”你就能从相遇可能性、位置限制、环入口推导三个层面逐个回答。快慢指针的核心从来不是代码本身而是“用相对位移换取零额外空间”这个思想它值得你在更多场景里反复使用。