142. Linked List Cycle II

題目連結

思路

此題是關於 LinkedList 迴圈經典題目的小變形，除了需要判斷 LinkedList 是否有迴圈之外，還需要找出迴圈開始的節點位置在哪裡。一個比較直觀的方法是把走過的節點用一個 map 記錄起來，在每次走到一個新的節點的時候就回去 map 裡面檢查有沒有遇到同一個節點，沒有的話就把它加進去 map 然後繼續前進，否則就回傳該節點表示這個節點就是迴圈開始的地方，而如果順利走到 null 的話就表示沒有迴圈。實作上大概會是像下面這樣：

Golang

func detectCycle(head *ListNode) *ListNode {
    nodes := make(map[*ListNode]bool)

    ptr := head

    for ptr != nil {
        _, exists := nodes[ptr]
        if exists {
            return ptr
        }
        nodes[ptr] = true
        ptr = ptr.Next
    }

    return nil
}

不過這個方法的一個可以優化的地方是它所需要的空間複雜度會是 $O(n)$，如果想要使用更加節省空間的做法的話，就必須再度請出雙指標來協助啦~

在以往使用雙指標判斷一個 LinkedList 是否有迴圈的方式會利用快慢指標的方式來檢查，快指標會以慢指標兩倍的速度前進，如果 LinkedList 有迴圈的話那兩個指標一定會在迴圈裡相遇，否則快指標就會先一步抵達終點。但在加入了迴圈起始點的要求之後，整個狀況就會變得比較複雜，需要一點仔細的數學計算了。

上圖是在有迴圈的時候幾個關鍵節點，其中 a 代表從開頭到進入迴圈之前的距離，b 則是從迴圈起點到快慢指標相遇的節點之間的距離，c 則是迴圈當中剩餘的距離。對於快指標來說，在碰到慢指標之後，它所走過的距離會是 a + m(b + c) + b，這邊的 m 是它在迴圈裡所走過的圈數，而慢節點所走過的距離會是 a + b (關於慢指標為什麼一定只走了一圈以內的距離可以參考這篇文章的說明)。再加上另一個條件是快指標的移動速度是慢指標的 2 倍，也就是說快指標走的距離也同時會是 2(a + b)。

因此就可以列出 a + m(b + c) + b = 2(a + b) 這樣的關係式，稍微整理一下之後會變成 a = m(b + c) - b = (m - 1)(b + c) + c，當 m = 1 時 (代表快指標只走一圈) 就和慢指標相遇，此時會得到 a = c 的關係，也就是說在 meet 和 head 兩個位置同時放兩個指標，並以相同的速率一次一個節點前進，那麼兩者相遇的位置就會是迴圈開始的節點，具體的演變可以參考下面的動圖~

Full Code

Golang

func detectCycle(head *ListNode) *ListNode {
    fast := head
    slow := head

    for fast != nil && fast.Next != nil {
        fast, slow = fast.Next.Next, slow.Next

        if fast == slow {
            fast = head
            for fast != slow {
                fast, slow = fast.Next, slow.Next
            }
            return fast
        }
    }

    return nil
}