链表中环的入口节点（Java,剑指思路）

双指针法
1，确定一个链表中包含环
定义两个指针，同时从链表的头节点出发，一个指针每次走一步，另一个指针每次走两步；如果快指针追上了慢指针，那么链表就包含环。

2，得到环中节点数目
两个指针相遇的节点一定在环中，从这个节点出发，一边继续向前移动一边计数，再次回到这个节点时，就可以得到环中结点的数目。

3，找到环的入口
先定义两个指针P1,P2指向头节点。如果链表环中有n个节点，则指针p1先向前移动n步，然后两个指针以相同的速度向前移动。当第二个指针指向环的入口节点时，第一个指针已经绕着环走了一圈回到了入口节点。

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

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode MeetNode(ListNode pHead){
        if(pHead == null){
            return null;
        }
        ListNode pslow = pHead.next;
        if(pHead.next == null){
            return null;
        }
        ListNode pfast = pslow.next;
        while(pfast != null && pslow != null){
            if(pfast == pslow ){
                return pfast;
            }
            pslow = pslow.next;
            pfast = pfast.next;
            if(pfast != null){
                pfast = pfast.next;
            }
        }
        return null;
    }

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        ListNode meetingNode = MeetNode(pHead);
        if(meetingNode == null){
            return null;
        }
        int nodesInLoop =1;
        ListNode p1= meetingNode;
            while (p1.next != meetingNode){
                p1=p1.next;
                ++nodesInLoop;
            }
        p1=pHead;
        for(int i=0; i< nodesInLoop; ++i){
            p1=p1.next;
        }
        ListNode p2 =pHead;
        while(p1 != p2){
            p1 = p1.next;
            p2=p2.next;
        }
        return p1;
    }
}