链表中环的入口结点_JAVA_中等

• 快指针走完了n圈，路径为A+(n - 1)B + nC，慢指针走了A+B（慢指针走一步则快指针离慢指针近一步，慢指针与快指针距离小于一圈，则慢指针不可能走完一圈）
• 有A+(n+1)B + nC = 2(A+B)，则A =(n-1)(B+C) + C
• 则相遇后快指针从起点出发，一次走一步，慢指针不变，两者则会相遇至环入口
• 图来自一颗闪闪发亮的马路星
• 

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        ListNode fast = pHead, slow = pHead;
        // 先找到相遇结点
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
                break;
            }
        }
        if(fast == null || fast.next == null) {
            return null;
        }
        // 找到入口
        fast = pHead;
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}