LeetCode 142.环形链表II：快慢指针法的直观理解与实现

创作时间:

作者:

@小白创作中心

LeetCode 142.环形链表II：快慢指针法的直观理解与实现

引用

CSDN

https://m.blog.csdn.net/laodanqiu/article/details/145807853

环形链表II

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/

如何判断链表存在环

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

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

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

怎么知道环入口在哪

假设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)

代码实现

为啥判断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;
}