[LeetCode] Linked List Cycle 2

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

解题思路：
1. 延续linked list cycle1的题目，先用两个指针p, pn分别走一步和2步，则它们相遇的时候，等于
    n = m*Y  (Y为圈的长度，n为移动一位走的步数)
   如果假设它们相遇的位置离圈开始的那个地方为k，则有，x + k ＝ n (x 为非圈的点数)。
   也就是说 x + k = m*Y. 也就是p再往后走x步就到达了圈开始的结点。

如果此时我们再从头开始一个指针一起往后走，则走x步，它们会在圈开始的结点处相遇

Java Code

 ListNode p = head;
        ListNode pn = head;
        
        while(p != null && pn != null && pn.next != null){
            p = p.next;
            pn = pn.next.next;
            
            if(p != null && p == pn){
                ListNode pre = head;//set another pointer to the beginning
                
                while(p != pre){
                    p = p.next;
                    pre = pre.next;
                }
                return pre;
            }
        }
        
        return null;