题目描述

一个链表中包含环，请找出该链表的环的入口结点。要求不能使用额外的空间。

解析:快慢指针。快慢指针相遇时，快指针走了2k长度，慢指针走了k长度。多的k长度就是环的长度。假设相遇点距离环入口为m，则环入口距离起始点为k-m，恰巧相遇点的指针再走k-m节点就为环入口。所以同时继续出发，再次相遇点就是环的入口。

public ListNode EntryNodeOfLoop(ListNode pHead) {
 	if (pHead == null || pHead.next == null)
  		return null;
   	ListNode slow = pHead, fast = pHead;
    do {
   		 fast = fast.next.next;
         slow = slow.next;
      } while (slow != fast);
     fast = pHead; 
     while (slow != fast) {
       	 slow = slow.next; 
         fast = fast.next;
      }
         return slow;
   }