給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 null。

為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。

說明：不允許修改給定的鏈表。

示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：tail connects to node index 1
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。

示例 2：
輸入：head = [1,2], pos = 0
輸出：tail connects to node index 0
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。

示例 3：
輸入：head = [1], pos = -1
輸出：no cycle
解釋：鏈表中沒有環(huán)。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

/**
*思路：
1.先新建兩個指針分別指向頭部
2.慢指針p1每次走一步，快指針p2每次走兩步
3.如果存在環(huán)，那么快指針跟慢指針一定會相遇在環(huán)的某個點P
4.假設(shè)起點到入環(huán)點的距離為D，入環(huán)點到第一次相遇點的距離為S1，環(huán)的剩余長度為S2，
  因為環(huán)走一圈會回到原點
5.這樣可計算相遇時  P1走的長度為 D + S1,P2走的長度為 D + S1 + n(S1 + S2)
6.由2可知P2走的距離是P1的兩倍，所以得到 2（D + S1） =  D + S1 + n(S1 + S2)
  化簡可得D = (n - 1)(S1 + S2) + S2;從移動距離來講，S1+S2=0,所以D = S2;
7.所以當(dāng)p1和p2相遇后，將p2放回原點，p1和p2按1步走，再次相遇的點就是入環(huán)點
  
*/
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null){
            return null;
        }
        if(head.next.next == head) 
            return head; 
        
        ListNode p1 = head;
        ListNode p2 = head;
        
        //是否相遇
        boolean meet = false;
        
        while( p2.next != null && p2.next.next != null){
            if(!meet){
                 p1= p1.next;
                 p2 = p2.next.next;
            }else{
                 p1= p1.next;
                 p2 = p2.next;
            }
           
            //第一次相遇,要把快指針p2放回起點
            if(p1 == p2 && !meet ){
                meet = true;
                p2 = head;
            }
            //第二次相遇
            else if(p1 == p2 && meet){
                return p1;
            }
            
        }
        return null;
        
    }
}