链表中环的入口节点

双指针解法

前置思想（以下长度指节点数量）
假设环的长度为k，链表长度为n，那么环的入口节点的前面的长度则为n-k。我们可以用两个指针left和right，先让right向前走k步，此时它距离链表终点的长度为n-k。然后我们再让这两个指针同步前进，当他们相遇时，所在节点即为环的入口。

1. 首先利用快慢双指针，判断链表是否存在环(两个节点相遇时即存在环)，不存在则立即返回null，否则接着下一步。
2. 两个节点相遇时是在环里面，因此可以让慢节点静止不动，让快节点从慢节点开始向前移动并计数，当相遇时的计数便是环的长度。
3. 利用left和right两个指针，left在起始点，让right先走k步，然后两个指针再同步前进，等到相遇时的节点即为环的入口。

public ListNode EntryNodeOfLoop(ListNode pHead)
 {
        if(pHead==null||pHead.next==null)
            return null;
        ListNode slow=pHead,fast=pHead.next.next;
        // check whether the list has circle
        while(slow!=null&&fast.next!=null&&slow!=fast){
            slow=slow.next;
            fast=fast.next.next;
        }
        if(slow==null||fast==null)
            return null;
        // length of circle
        int k=1;
        fast=slow.next;
        while(slow!=fast){
            k++;
            fast=fast.next;
        }
        slow=pHead;
        fast=pHead;
        // move forward k steps
        for(int i=0;i<k;i++){
            fast=fast.next;
        }
        //move forward synchronously
        while(slow!=fast){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;


    }