思路

这是【单链表中是否有环，写出代码】的扩展题，可以划分到面试中难度最大的那一档中

没有思路，只能静下心来 

找环的入口点，就是找到入口点是链表的第几个结点，设这个结点q是第a个,

head到q的长度是a, 两个指针相遇时离入口点的距离为t, 链表长度为L，环的长度为r

如果相遇，设slow走了s步，则fast走了2s

可得 2s = s+ nr ( n >= 0)

=> s = nr => a + t = nr => a + t = (n-1)r + r 

=> a + t = (n -1)r + L – a => a = (n-1)r + (L – a – t) 

L – a – t 为相遇点到环入口点的距离

得到结论

设置两个指针，一个放在相遇点，一个放在链表头结点，当两者第一次相遇时，就得到环入口点P

实在不理解，可以只记住这个结论

代码

Node findLoopNode(Node head)
{   //先找到相遇点，与例三一致
  Node slow = head, fast = head;
  
  while ( fast && fast.next )
  {
    slow = slow.next;
    fast = fast.next.next;
    if ( slow == fast ) break;
  }
  if (fast == null || fast.next == null);
    return null;    
   //从相遇点开始到与头结点相遇
  slow = head;
  while (fast != slow)
  {
    fast = fast.next;
    slow = slow.next;
  }
  return fast;
}