給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。 從鏈表的頭節(jié)點開始沿著 next 指針進入環(huán)的第一個節(jié)點為環(huán)的入口節(jié)點。如果鏈表無環(huán)，則返回 null。

為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意，pos 僅僅是用于標識環(huán)的情況，并不會作為參數(shù)傳遞到函數(shù)中。

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

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節(jié)點
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。

示例 2：

輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節(jié)點
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。

示例 3：

輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環(huán)。

提示：
鏈表中節(jié)點的數(shù)目范圍在范圍 [0, 104] 內(nèi)
-105 <= Node.val <= 105
pos 的值為 -1 或者鏈表中的一個有效索引

進階：是否可以使用 O(1) 空間解決此題？

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/c32eOV
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解題思路及方法

O(n)的空間是使用HashSet來記錄已經(jīng)訪問的節(jié)點，比較容易實現(xiàn)，我們僅考慮O(1) 空間。

先考慮有環(huán)情況下，我們使用快慢指針，快指針每次走兩步，即兩個節(jié)點，慢指針每次走一步， 即一個節(jié)點，那么在有環(huán)的情況下，快慢指針肯定會相遇，而且是在慢指針沒有走完第一圈的情況下相遇，并且快指針永不為空，否則沒有環(huán)。我們首先推導(dǎo)為什么是第一圈：

• 快指針先進入環(huán)；
• 當(dāng)慢指針剛到達環(huán)的入口時，快指針此時在環(huán)中的某個位置（也可能此時相遇）；
• 設(shè)此時快指針和慢指針距離為x，若在上一步相遇，則x = 0；
• 設(shè)環(huán)的周長為n，那么看成快指針追趕慢指針，需要追趕n-x；
• 快指針每次都追趕慢指針1個單位，設(shè)慢指針速度1/s，快指針2/s，那么追趕需要(n-x)s；
• 在n-x秒內(nèi)，慢指針走了n-x單位，因為x>=0，則慢指針走的路程小于等于n，即走不完一圈就和快指針相遇。
  當(dāng)快慢指針相遇后，我們用指針idx指向鏈表頭部，idx和慢指針同時一次移動一步，當(dāng)它們相遇時，即環(huán)入口，推導(dǎo)：

我們設(shè)頭部到環(huán)入口長度為a，快慢指針相交時慢指針從環(huán)入口走了長度b，快指針從環(huán)入口走了長度b+c+b=2b+c，則慢指針總共走了a+b，快指針總共走了a+2b+c。由于快指針速度時慢指針2倍，所有有如下公式：

• 2(a+b) = a+2b+c
  推出：a=c，這也是為什么慢指針走c步，idx走a步，兩個指針到達環(huán)入口處。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        // 快慢指針，快指針一次移動兩步，慢指針一次移動一步
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) fast = fast.next.next;
            // 不存在環(huán)
            else return null;
            
            // 存在環(huán)，指針相遇
            if (fast == slow) {
                ListNode idx = head;
                while (idx != slow) {
                    slow = slow.next;
                    idx = idx.next;
                }
                return idx;
            }
        }
        
        return null; 
    }
}

結(jié)果如下：