环形链表II 超直观的理解思路

🎯 本文详细解析了链表环问题“环形链表II”的解决方案。通过快慢指针法，介绍了如何判断链表是否存在环以及如何找到环的入口节点。核心思想是利用速度差使快指针追上慢指针以确定环的存在，并通过数学推导证明了从头节点和相遇点同时出发的两个指针必将在环入口相遇。文章还提供了Java代码实现及复杂度分析，时间复杂度为O(n)，空间复杂度为O(1)。

环形链表II

如何判断链表存在环

使用两个指针，一个快指针fast，一个慢指针slow。两者都从链表头节点开始遍历，但是fast一次走两步，slow一次走一步。

如果存在环的话，fast一定会追上slow。为什么？

想象苏炳添在操场上一直跑圈，你无论时候上去跑，一开始距离苏神多远，最终都会被苏神追上。为什么，因为他跑得比你快呀。

当然如果fast还追上slow，一直遍历到null，这就说明链表不存在环

怎么知道环入口在哪

alt

假设fast跑了 n 圈，和slow在相遇点相遇。此时两者走过的距离：

slow走过的距离：(x+y)
fast走过的距离：x+y+n(z+y)

因为fast的速度是slow的两倍，所以fast走过的距离是slow距离的两倍，即2(x+y)=x+y+n(z+y)。经过化简之后，x=(n-1)(z+y)+z

化简过程： 2(x+y)=x+y+n(z+y) 左右约掉(x+y) -> x+y = n(z+y) y 移到右边 -> x = nz+ny-y -> x = nz+(n-1)y x = (n-1)z+z+(n-1)y x=(n-1)(z+y)+z

若n=1，即fast只多走了 1 圈，则x=z
若n>1，即fast多走了几圈，则x=(n-1)(z+y)+z。看这个公式
- 公式左边x：就是节点从连接头节点到环入口的距离
- 公式右边(n-1)(z+y)+z：可以理解为节点从相遇点出发，走了n-1圈，再走到环入口的距离

从这个公式可以得到什么启发？

即一个指针从链表头节点出发，一个指针从相遇点出发，两个指针的速度一样，最终一定会在环入口相遇，那通过这种方式，相遇的时候就知道环入口是哪个节点了

为什么相遇的时候，`slow`的距离是`(x+y)`

为什么相遇的时候，slow不能走了几圈呢，为什么不能是x+ny？

想象一下，slow进环的时候，fast肯定已经在环中了。

如下图所示，将环展开，slow进环的时候，假设fast的位置在A。那当slow下一次到进环点时，即位置B。由于fast的速度是slow的两倍，距离也是两倍，即L2=2L1，那么此时 fast的位置在C。因此在slow到达B之前，fast一定和slow相遇过了，因此slow绝对没走完一圈，所以距离是(x+y)

alt

代码实现

为啥判断 fast 不为空，不用判断 slow 不为空?

因为fast指针更快，假设不存在环的话，肯定是fast先遍历到 null 。因此如果fast都不为null，slow怎么可能是null，所以无需判断

如何判断快慢指针是否相遇

直接用slow == fast判断即可，因为两个指针指向的是同一个对象，因此引用的内存地址是一样的，所以直接判断即可

public static ListNode detectCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null) {
        // --if-- fast不为null，才继续进行
        // slow指针前进一步
        slow = slow.next;
        // fast指针前进一步
        fast = fast.next;
        if (fast == null) {
            // --if-- fast为null，说明不存在环，直接返回null
            return null;
        }
        // fast指针再前进一步
        fast = fast.next;

        if (slow == fast) {
            // --if-- 快慢指针相遇，找到相遇点
            // 将慢指针移动回链表头节点，快指针从相遇点出发
            slow = head;
            while (true) {
                if (slow == fast) {
                    // --if-- 快慢指针重新相遇，说明找到了环入口节点，直接返回
                    return slow;
                }
                // 两个指针以同样的速度前进
                slow = slow.next;
                fast = fast.next;
            }
        }
    }
    // fast走着走着为 null 了，退出循环，则说明没有环，返回 null
    return null;
}