LeetCode 141. 环形链表：快慢指针与「为什么一定会相遇」

题目与解法的直觉

LeetCode 141：判断链表是否有环（某节点的 next 指回之前的节点）——O(1) 空间判断。

「为什么要判断环」：环导致遍历无限循环（「next 指回之前的节点」——while 循环永不结束——「有环 = 无法自然终止」——「哈希表判环」：访问过的节点存 set——重复出现即有环——「O(n) 时间 O(n) 空间」——「哈希的方案」简单正确——「O(1) 空间」的挑战——「快慢指针」的登场。

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next          # 慢指针：一步
        fast = fast.next.next     # 快指针：两步
        if slow == fast:
            return True
    return False                  # fast 到尾 = 无环

「为什么一定会相遇」的证明

「相对速度」的直观解释：快指针每轮比慢指针多走 1 步——「相对速度 1」——进入环后，快指针「追」慢指针——「每轮距离缩短 1」——「一定追上」——距离有限（环长 k）——每轮缩 1——k 轮内必然相遇——「不可能跳过」：相遇时快指针在慢指针前 j 个位置——「距离每轮减 1」——从 j 缩到 0——「恰好相遇而不是跳过」——「相对速度为 1」的巧妙（如果快指针走 3 步——相对速度 2——可能跳过（距离从 2 直接到 0 的下一个是 -1（模环长——「速度 2」可能错开——「速度差为 1」保证逐格逼近——「这也是为什么 fast 走两步不是三步」——「两步」的设计有数学保证。

「环内相遇」的严格论证：进入环后（慢指针进入环——快指针已在环内——「快指针相对于慢指针的位置」——每轮 +1（模环长 k——「从某个初始差 d 出发」——d, d+1, d+2, ..., mod k——「必然经过 0」（d 在 [0, k-1] 中、每次 +1 模 k——「0 就是相遇」——「最多 k 轮」内相遇——「相遇的轮数上界」= 环长——「复杂度：O(n)」（慢指针走的总步数（入环前 n 步 + 环内最多 k 轮——「总时间」= O(n)——「空间的 O(1)」：两个指针——「哈希法 O(n) 空间」vs「快慢法 O(1) 空间」——「空间优化」的经典案例。

graph TD
    A[快慢指针入环] --> B[相对速度 1<br/>每轮距离缩短 1]
    B --> C[距离有限 → k 轮内相遇<br/>不可能跳过]
    C --> D[时间 O(n) · 空间 O(1)]

进阶：找入环点（LeetCode 142）

「判断有环」升级为「找到环的入口」——「哈希法轻松」（set 里第一次重复的就是入口——「快慢指针怎么做」——「数学推导」的精彩：「相遇点」的几何——设入环前有 a 步、环长 k——「慢指针入环时」走了 a 步——「快指针已在环内走了 a 步」——「快相对慢多走 2a-a = a」——「相遇时」：快指针在环内走了 (a + x) 步——「慢指针在环内走了 x 步」——「快 = 2 × 慢」（快指针总步数是慢指针的 2 倍——「2(a+x) = a + x + m·k」（m 圈的修正——「解出 x = m·k - a」——「相遇点距入环点 = k - x = a mod k」——「关键结论：从相遇点再走到入环点的距离 = 从起点走到入环点的距离」——「两个指针同速」：一个从头、一个从相遇点——「同速前进」——「再次相遇的点就是入环点」——「这个推导」是算法面试的经典考题——**「数学的味道」在算法中的呈现。

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow == fast:                 # 相遇
            slow = head                  # 慢指针回起点
            while slow != fast:          # 同速前进
                slow, fast = slow.next, fast.next
            return slow                  # 入环点
    return None

「Floyd 判圈」的统一：「Floyd's cycle detection（龟兔赛跑）」——快慢指针判环+找入口——「287 题（寻找重复数）的复用」（库内已有专文——「把数组当链表」（nums[i] 作为下标跳转——「同一个数学」——「判圈算法的迁移」——「一个算法、多个伪装」。

数据迁移的进阶：迁移的「前置设计」与「分库分表的迁移」

数据迁移的进阶：迁移的前置设计与分库分表场景的特殊迁移。「迁移的前置设计」：「迁移前的评估」：「数据量与窗口」（数据量决定迁移方式——「亿级」用工具、「千万级」可用脚本——「主从延迟的容忍」（gh-ost 的限速——「迁移的预估时间」——「迁移方式的选择树」（数据量×DDL 类型→工具选择——「选择树」：小表 online DDL、大表 gh-ost、跨库迁移双写——「选择树」的决策路径。「分库分表的迁移特殊性」：「分片的迁移」：「单库到分库」（迁移+分片同时——「ShardingSphere 的迁移工具」——「分片键的确定」（迁移前必须定好——「分片键错误」的不可逆——「分片键的决策」在迁移前的评估——「分片迁移的双写」（新旧双写的复杂度翻倍——「分片双写」的挑战——「分片迁移」是大迁移——「大迁移」的里程碑管理——「里程碑」：双写→存量→切读→切写→下线——「五个里程碑」的逐步推进——「每一步的验证」——「验证」是里程碑的出口——「验证不过不进下一步」。「迁移的「组织管理」：「迁移不是一个人的事」：「迁移的角色」：迁移负责人、DBA、业务方、QA——「迁移的沟通」——「迁移的窗口协调」（业务方的低峰配合——「迁移的检查清单」——「迁移的 checklist」（20 项的清单——「checklist」的逐项确认——「迁移的 postmortem」（迁移后的复盘——「复盘」的沉淀——「迁移的 SOP」——「SOP」的形成——「下一次迁移」更快更稳——「迁移的经验」变成组织的资产。数据迁移的进阶总结：前置设计的选择树（数据量×DDL→工具）+分库分表迁移的特殊性（分片键先行、双写翻倍、五里程碑）+组织管理（角色、checklist、SOP）——「数据迁移」是工程中的「心脏手术」——「手术的成功」=术前评估（选择树）+术中监控（里程碑验证）+术后恢复（SOP 沉淀）——「迁移的每一个环节」都要有预案——「预案」是迁移工程师的安全网——「安全网」越多，迁移越稳。

快慢指针的变奏：中点、倒数第 N 与「步长的数学」

141 的「判环」只是快慢指针的第一个应用，这个家族还有三个高频成员，共用同一个心智：两个指针保持固定的相位差或速度差，用位移关系换信息。「找中点（LeetCode 876）」：快走二慢走一，快到尾时慢在中点——细节在偶数长度：这个写法返回的是第二个中点（1,2,3,4 返回 3）；如果要第一个中点（比如链表归并排序想把左半拆短一点），让 fast 从 head 的下一个节点起步，或把循环条件改成「fast 的下下个非空」——「中点偏左偏右」是链表分割类题目的隐形分叉，写归并排序前先确认要哪一个。「删除倒数第 N 个（LeetCode 19）」：快指针先走 N 步建立相位差，然后双指针同速前进，快指针到尾时慢指针正好停在倒数第 N+1 个节点上——配合 dummy 头，删除动作退化成一句「改 next 跳过被删节点」；两个易错点：N 等于链长（删头）时，dummy 的存在让特判消失（呼应 15 篇的 dummy 家族）；「先走 N 步」到底是 N 还是 N+1，取决于你想让慢指针停在「被删节点」还是「被删节点的前驱」——删除需要前驱，所以标准写法先走 N+1 步。「组合拳：重排与回文」：LeetCode 143（重排链表）与 234（回文链表）都不引入新的指针技巧，而是三件套的组合——快慢找中点、反转后半段、双指针对比或交错合并；链表归并排序同样以「找中点 + 断开」为分割步骤——快慢指针的价值常常不是独立解题，是组合里的标准零件。「步长的数学」：正文说过快指针走三步（相对速度 2）可能跳过慢指针，这里给出精确条件——设进入环后的初始距离 d0、环长 k、相对速度 v，每轮距离按「d 减 v 再对 k 取模」递减，可达集合是 d0 所在的「gcd(v, k) 同余类」——相遇当且仅当 gcd(v, k) 整除 d0：v=2、k=6、d0=3 时，距离永远在 3、5、1、3…… 打转，永不相遇；v=1 时 gcd 恒为 1，任何 d0 都能到达 0——这就是「相对速度为 1」不是惯例而是定理的原因。顺带的推论：判环时慢指针在环内最多 k 轮必被追上，整体时间上界是「尾部长度 + 环长」= O(n)。最后留一个迁移练习：数组的下标跳转找环、「快乐数」的平方和链——它们都没有显式的 next 指针，但都满足「确定性单后继」，快慢指针照用不误——判断能不能用快慢指针的标准，从来不是「是不是链表」，是「是不是单路径的确定性状态转移」。

「循环条件为什么写 while fast and fast.next 而不是判 slow？」——因为可能越界的只有 fast：它每轮跳两步，null 检查必须同时覆盖「fast 本身为空」与「fast.next 为空」两种；slow 每轮只走一步、永远跟在 fast 后面，fast 合法则 slow 必合法——判空的顺序跟着「谁会越界」走，顺序写反（先比较后判空）就是空指针。「快慢指针与滑动窗口是什么关系？」——同族而不同名：滑动窗口是「同向双指针保持动态间距」，快慢指针是「固定速度差或固定相位差」；共同的心智是用两个指针的相对运动编码信息——窗口的左右边界在数组上滑动，快慢的相位差在链表上前进，前文的重排、回文、倒数第 N 全是相位差的不同取值——把「同向双指针」当成一个大家族，判环、找中点、删倒数第 N 就共享同一份直觉。

小结

环形链表的完整解析：快慢指针判环（相对速度 1——「必然相遇且不跳过」——O(n) 时间 O(1) 空间——「哈希法」的简单正确与「快慢法」的空间优雅）；找入环点的数学（快=2×慢的距离方程 → 「相遇点距入口 = 起点距入口」——同速前进二次相遇——Floyd 判圈的完整推导）；判圈算法的迁移（287 题「数组当链表」——「一个算法、多个伪装」）；设计细节（「fast 走两步」的数学保证、「先判 fast 再判 slow==fast」的空指针顺序——「判空的顺序」：fast 与 fast.next——「先 fast 后 next」防 NPE。给学习者的两个提醒：「判环」的最佳实践是快慢指针+哈希兜底——快慢指针为主（省空间）、面试追问时提哈希（简单正确）——以及，「入环点的数学推导」值得手推一遍——「2(a+x) = a + x + m·k」这一行方程，是「算法之美」的教科书展示——它证明的不是「能工作」，是「为什么必然工作」**——数学保证正确，工程负责实现。

快慢指针判环的思想，从链表延伸到数组、延伸到「快乐数」的数字循环、延伸到状态的循环检测——「检测状态图中的环」——是所有「无限循环」问题的通用解法——龟兔赛跑，跑的是一切有环的状态图。