02. Linked List Cycle II

読了目安約2分

Linked List / LeetCode 142 (Medium) — 循環が始まるノードをフロイドの循環検出法で特定する。

この章の目次

問題

LeetCode 142. Linked List Cycle II（Medium / カテゴリ: Linked List）

循環を持つかもしれない連結リストの先頭 head が与えられます。循環があるとき、循環が始まるノード（たどっていて最初に 2 回目の訪問が起きるノード）そのものを返してください。循環がなければ nil を返します。

考え方

ヒント 1

訪れたノードを順に記録していくと、最初に 2 回現れたノードが循環の入口です。 141 が解けていれば、記録を Set に置き換えるだけでこの方針は完成します。

ヒント 2

追加メモリなしで解くのがフロイドの循環検出法です。速い・遅いポインタが出会ったら、片方を先頭に戻し、両方を 1 歩ずつ進めます。先頭から入口までの距離と、出会った地点から入口までの距離は循環の長さを法として等しいため、2 つは入口でちょうど出会います。

Swift 実装のポイント

返すのは「値」ではなくノードそのものです。テストコードは === で同一性を比べます。
出会いを探すループは 141 と同じ形です。出会った後に、1 歩ずつ進める 2 本目のループを足します。
2 本目のループは while start !== slow のように、参照が一致するまで回します。

模範解答

Swift
class Solution {
    func detectCycle(_ head: ListNode?) -> ListNode? {
        var slow = head
        var fast = head
        while fast != nil && fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
            if slow === fast {
                var start = head
                while start !== slow {
                    start = start?.next
                    slow = slow?.next
                }
                return start
            }
        }
        return nil
    }
}

計算量: O(n) 時間、O(1) 追加メモリ。