BM7题解 | #链表中环的入口结点#

双指针解决环的入口

思路来自代码随想录

我们把整个路径分为三段：

第一段：没有环的，x

第二段：环的入口到相遇的地方，y

第三段：相遇的地方到入口，z

定义两个指针：

fast指针：一次走两格

slow指针：一次走一格

两个指针都从head触发，最后一定会在环内相遇，因为fast每次都比slow多走一格

再定义两个指针:

p1从head出发，p2从相遇的地方出发，每个指针一次都走一格，最后会在入口处相遇

请看如下证明：

slow走的节点个数为 x + y

fast走的节点个数为 x + y + n(y + z)，因为fast走得快，可能在环内走了n圈才和slow相遇

因为fast一次走两格，slow一次走一格，所以fast走的节点个数是slow的两倍，有：2(x+y) = x + y + n(y + z)

两边都消掉一个 x + y，得到 x + y = ny + nz -> x = (n-1) y + nz --> x = (n-1) y + (n - 1) z + z

为什么最后要拆一个z出来呢？z是从相遇的节点到入口的距离， y + z 正好是环内一圈的距离，这样就有

x = (n - 1) (y + z) + z

x的距离，也就是head到入口的距离正好等于 n - 1 圈的距离 + 相遇的点到入口的距离，那么p1 和 p2就一定会在入口处相遇

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode fast = pHead;
        ListNode slow = pHead;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) { // 遍历过程中一旦相遇则说明有环
                ListNode p1 = pHead;
                ListNode p2 = fast;
                while (p1 != p2) {
                    p1 = p1.next;
                    p2 = p2.next;
                }
                return p1;
            }
        }
        return null;
    }
}