环形链表 II

🟡 Medium · 🏷️ 链表、双指针、快慢指针 · LeetCode#142

📖 题目

判断链表是否有环，如果有，返回环的入口节点；无环返回 None。

💡 思路

分两步：先用判断有没有环同样的快慢指针找到相遇点；然后从相遇点出发，让其中一个指针回到 head，两个指针都改成每次走一步，再次相遇的地方就是环的入口。

为什么第二步有效，简单推一下：设 head 到环入口距离 a，环入口到相遇点距离 b，相遇点绕回环入口距离 c。相遇时慢指针走了 a+b，快指针走了 a+b+n(b+c)（多绕了 n 圈），又因为快指针速度是慢指针的两倍：

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

也就是说，从 head 走 a 步，和从相遇点走 c 步（可能多绕几圈），会在同一个地方停下——都是环入口。所以两个指针同步一步步走，必定在入口相遇。

💻 代码

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:        # 找到相遇点
                slow = head
                while fast != slow:  # 同步走找入口
                    fast = fast.next
                    slow = slow.next
                return slow
        return None                  # 无环

时间复杂度 O(n)，空间复杂度 O(1)。这个套路是数学推导出来的结论，记住结论就好，不用每次重新推。