23、链表中环的入口结点

题目：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4

/*
 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) return null;
        ListNode meetNode = meetNode(pHead);      // 有环则为相遇节点，否则为null
        if(meetNode==null) return null;
        int nodeSize = 1;                         // 环的长度
        ListNode current = meetNode.next;         // 计算环的长度
        while(current != meetNode){
            ++nodeSize;
            current = current.next;
        }

        // 节点current先往前走nodeSize（环的长度），然后再和behind一起往前走，这样能够保证相遇节点是环的入口节点（ps：想想为什么）
        ListNode behind = pHead;
        current = pHead;  
        while(nodeSize-->0){                                
            current = current.next;
        }
        while(behind!=current){
            behind = behind.next;
            current = current.next;
        }
        return current;
    }
    
    // 判断是否存在环，若有则返回相遇节点，否则返回null
    private ListNode meetNode(ListNode pHead){
        ListNode slow = pHead;
        ListNode fast = pHead;
        while(fast.next!=null){
            fast = fast.next;
            if(fast==null) return null;
            fast = fast.next;
            if(fast==null) return null;
            if(fast==slow) return fast;
            slow = slow.next;
        }
        return null;
    }
}