LeetCode 75 學習計劃适用于想為技術面試做準備但不确定應該聚焦于哪些題目的使用者。學習計劃中的題目都是經過精心挑選的，Level 1和 Level 2 學習計劃是為初級使用者和中級使用者準備的，題目覆寫了大多數中層公司面試時所必需的資料結構和算法，Level 3 學習計劃則是為準備面試頂級公司的使用者準備的。​​來源​​

第 5 天

​​環形連結清單 II​​

難度：中等

題目

給定一個連結清單的頭節點  head ，傳回連結清單開始入環的第一個節點。 如果連結清單無環，則傳回 null。

如果連結清單中有某個節點，可以通過連續跟蹤 next 指針再次到達，則連結清單中存在環。 為了表示給定連結清單中的環，評測系統内部使用整數 pos 來表示連結清單尾連接配接到連結清單中的位置（索引從 0 開始）。如果 pos 是 -1，則在該連結清單中沒有環。注意：pos 不作為參數進行傳遞，僅僅是為了辨別連結清單的實際情況。

不允許修改 連結清單。

輸入： head = [3,2,0,-4], pos = 1
輸出： 傳回索引為 1 的連結清單節點
解釋： 連結清單中有一個環，其尾部連接配接到第二個節點。      

題解

判斷一個連結清單是否成環。

function ListNode(val){
    this.val = val
    this.next = null
}      

我們使用兩個指針，fast 與 slow。它們起始都位于連結清單的頭部。随後，slow 指針每次向後移動一個位置，而 fast 指針向後移動兩個位置。如果連結清單中存在環，則 fast 指針最終将再次與 slow 指針在環中相遇。

然後把快指針放到頭，和慢指針一起走，他們再次相遇的位置就是環的入口！

為什麼是這樣？我們可以參考下圖：

設環的入口是 L 長度，那麼慢指針走的距離是 L，快指針走的則是 2L，設整個路徑長度是 D，第一次相遇的距離是 D - L，剩下的距離是 (D-(D-L))，也就是 L ，這也就解釋了為什麼 設的 L 是對的。

這裡有個視訊講解，很清晰。-> ​​https://leetcode.cn/problems/linked-list-cycle-ii/solution/142-huan-xing-lian-biao-ii-by-chen-wei-f-g157/​​

var detectCycle = function(head) {
    if (head === null) {
        return null;
    }
    let slow = head, fast = head;
    while (fast !== null) {
        slow = slow.next;//慢指針移動兩步，快指針移動一步
        if (fast.next !== null) {
            fast = fast.next.next;
        } else {
            return null;//如果沒有環 之間傳回null
        }
        if (fast === slow) {//有環
            let fast = head;
            //快指針指向頭節點，然後每次快慢指針各走一步直到相遇，相遇的節點就是入環節點
            while (fast !== slow) {
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
    }
    return null;
};      

總結