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

基本思路

如果链表中有环，经过数学推导，当两者相遇时，链表从开头到相遇点的距离刚好等于环的整数倍大小，所以当两者相遇时，将快指针重置到开头，慢指针停在相遇点，然后两者开始一步一步的遍历链表，最终会同时经过环入口到达相遇点，因此再次遍历时两个指针相遇的地方就是环入口。

参考

参考题解

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

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    private ListNode hasCycle(ListNode pHead) {
        if (pHead == null) {
            return null;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                return slow;
            }
        }

        return null;
    }
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow = hasCycle(pHead);  // 如果有环，slow指针停在两者相遇的地方
        ListNode fast = pHead;  // fast指针停在开头

        if(slow == null) {  // 没有环，直接返回null，不作此判断会进入下面的while循环，因为fast!=null可能成立
            return null;
        }

        // 两者继续遍历，再次相遇的地方就是环入口
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }
}