环路检测分析 - 图1

    • slow 指针每次移动一位,fast 指针每次移动 2 位。

    • 如果相遇,则说明链表存在环。

    • 由 fast 指针移动距离为 slow 的两倍可得:

    • a + (nb + nc + b) = 2(a + b)

    • 变换处理后得到:

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

    • 新指针 ptr 从 head 开始移动,与 slow 相遇的位置即为环的起 点。