环形链表

问题拆解

判断链表里有没有环。最直白的办法是用一个集合记录走过的节点，每到一个节点就查它是否出现过，重复出现就说明成环。这样能做，但要额外 O(n) 的空间。

进阶要求 O(1) 空间。既然不能记录走过的节点，就得换个思路：让两个速度不同的指针在链表上跑，用它们的相对位置来判断有没有环。

慢指针一次走一步，快指针一次走两步。如果没有环，快指针会先冲到 None；如果有环，两个指针迟早会在环里相遇。

快慢指针

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

循环条件必须同时检查 fast 和 fast.next，因为快指针要连走两步，这两个位置都不能是空。一旦 fast 或 fast.next 为空，说明走到了链表尽头，无环。

为什么一定相遇

进入环之后，两个指针都在环里绕圈。把它们的距离看成“快指针要追上慢指针还差几步”，每一轮慢走一步、快走两步，这个差距就减少一格。差距是有限的整数，每轮减一，必然会减到零——也就是两指针落在同一个节点。它不会“跳过”慢指针，因为每轮只缩短一格，不可能一下从 1 跨到 -1。

复杂度

指标	复杂度	原因
时间	O(n)	慢指针进环后，最多再走一圈就被追上
空间	O(1)	只用两个指针，不额外记录节点

可以迁移的模式

• 判断链表有没有环、找环的入口、找中点，都可以用快慢指针；
• 关键在于设计两个指针的速度差，让它们的相对位置携带信息；
• 用 is 比较节点身份，而不是比较 val，因为值可能重复。

“两个指针不同速”是链表里非常通用的一招，值得当成模板记住。