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

做题心路：

首先我自己有推导过，但是，公式是错误的，以为是同一个节点或者上一个节点。但是，经过视频讲解后，发现是有公式的，

主要是，x+y == 是等于一个整数倍环的长度，而，y+z 就是一个环的长度，所以，也就是上面的公式：

x+y = k*(y+z)

所以，最终可以推导出， fast 指针从开头一步步走，和 slow指针在碰撞的地方，一步步走一定是可以相遇的。

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 slow = hasCycle(pHead);
        if(slow ==null) {
            return null;
        }

        ListNode fast = pHead;
        while(slow!=fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 判断链表是否有环
     * @param pHead待检查的链表
     * return 返回碰撞时的链表节点
     */
    ListNode hasCycle(ListNode pHead) {
        if(pHead==null) {
            return pHead;
        }
        ListNode slow = pHead;
        ListNode fast = pHead;
        while(fast!=null && fast.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) {
                return slow;
            }
        }
        return null;
    }
}