题解 | #链表中环的入口结点#

最经典的快慢指针题目

1. 快指针K一次走两步，慢指针M1一次走一步。
2. 两个指针第一次相遇时，快指针与慢指针都进入了圈内，假设相遇在Q点，而且快指针K比慢指针M1多走了一倍距离。
3. 如果这个时候让它俩都倒回去：慢指针原路倒回，快指针也原路倒回但倒回去的时候步伐改为1（和慢指针一样的步伐），那么当慢指针倒回到原点的时候，快指针才倒回倒Q点（正好还有一半要倒）。
4. 由第三步可知，如果不是倒回去，而是继续向前，即再派遣一个慢指针M2从原点出发，而同时让慢指针M1继续走，那么M2和M1必然会在Q点相遇的。
5. M2和M1其实在圈的入口点就第一次相遇了，之后同步走到Q点。所以M2等于M1的时候，就是圈的入口点。

具体代码如下：

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }

}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode p2 = pHead;
        ListNode p1 = pHead;
        do{ 
          	// 检查一下是否没有环
            if (p1 == null || p2 == null || p2.next == null) {
                // no found ring.
                return null;
            }
            p1 = p1.next;
            p2 = p2.next.next;
        }while(p1 != p2);  //直到快慢指针第一次相遇（圈内）
        ListNode p = pHead;
        while(p != p1) {
          	// 慢指针M1和慢指针M2第一次相遇
            p = p.next;
            p1 = p1.next;
        }

        return p;
    }
}