题解 | #链表中环的入口结点#借助环长度

/*
 public class ListNode {
    int val;
    ListNode next = null;

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

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead == null || pHead.next == null){
            return null;
        }
        //第一步 利用快慢指针判断是否有环
        ListNode fast = pHead;
        ListNode slow = pHead;
        boolean hasLoop = false;
        while(fast != null && fast.next  != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                hasLoop = true;
                break;
            }
        }
        if(hasLoop){
            //第二步 计算环的长度 既然fast 和 slow 已经相遇了 fast在走一圈不就是环的长度吗
            int loopLength = 1;
            fast = fast.next;
            while(fast != slow){
                loopLength ++;
                fast = fast.next;
            }
            //第三步 寻找入口节点  这里我们假设把环展开（环长度已经知道了），让一个指针A提前走一个环的长度
            //另一个指针B从头开始走 那么A走到头B刚好走到环节点的前一个位置 A和B再往前走就是环节点了（相遇即是环节点），因为展开是我们假设的
            fast = pHead;
            slow = pHead;
            //fast 先走一个环长度
            for(int i = 0;i < loopLength;i++){
                fast = fast.next;
            }
            while(fast != slow){
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        } else {
            return null;
        }
    }
}