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

判断单链表是否有环的升级版。

方法一

hash 存储遍历过的节点，如果出现重复便是起点，空间复杂度时O(n)，不满足要求。

方法二

快慢指针，slow每次走一步和fast每次走两步，如下图所示，两个指针同时从A出发，经过环的起点B，如果链表存在环，那边两个指针最终能够再C点相遇，假设慢指针经过B点后在环上经过了y个节点达到C点。此时：

slow走过的节点数=x+y, fast走过的节点数=2(x+y).

如果从C点向后退y个节点则刚好到B点。也就是说fast指针向后退 y 个节点就回到B点，那么也就是说从A出现经过 2(x+y)-y 可以达到B点， 2(x+y)-y=2x+y=slow+x，也就是说slow指针再向前走x步就达到环的起点。如何让slow指针向前走 x 步呢？

只需另起一个指针从A出发，如果这个指针再次与slow指针相遇，则说明slow指针恰好走了x步，这里就是环的起点B。

/*
 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, slow = pHead;
        while(fast != null) {
            slow = slow.next;
            fast = fast.next;
            
            if (fast == null || fast.next == null) {
                return null;
            }
            
            fast = fast.next;
            if (fast == slow) {
                break;
            }
        }
        fast = pHead;
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}