剑指offer 链表中环的入口结点

链表中环的入口结点

当慢指针到达环后，相当于快指针要追慢指针，最多需要追 (s-1) 个节点（s为环的长度）；
快指针速度是慢指针的2倍，所以每走一步差距减1；
所以慢指针最多走（s-1）步会被快指针追上。
如图，环的长度为5，fast最多只用追4个就能追上。

因为快指针减去慢指针为环的整数倍；
快指针速度是慢指针的2倍；
所以慢指针路程为环的整数倍。

慢指针：1，2，3，4，5， 6，7， 8， 9，10，11
快指针：1，3，5，7，9，11，8，10，12， 9，11
快慢指针会在p点相遇。

相遇时慢指针走的路程为 x+y，x+y 为环的整数倍，因此从p点开始，再走x步，会到达环的起点。

public class Solution {

  public ListNode EntryNodeOfLoop(ListNode pHead) {
    if (pHead == null) {
      return null;
    }

    ListNode fast = pHead;
    ListNode slow = pHead;
    while (fast != null && fast.next != null) {
      fast = fast.next.next;
      slow = slow.next;
      if (fast == slow) {
        ListNode p = pHead;
        while (p != slow) {
          p = p.next;
          slow = slow.next;
        }
        return p;
      }
    }

    return null;
  }
}