01. Linked List Cycle

読了目安 約2分

Linked List / LeetCode 141 (Easy) — 連結リストに循環があるかを速さの違う 2 つのポインタで判定する。

問題

LeetCode 141. Linked List Cycle（Easy / カテゴリ: Linked List）

連結リストは、各ノードが値と「次のノードへの参照」を持つデータ構造です。 その先頭ノード head が与えられます。 next をたどり続けるとどこかのノードへ戻ってくる（循環がある）とき true を、末尾の nil に到達するとき false を返してください。

考え方

Swift 実装のポイント

• ListNode は class で定義します。ノードどうしを参照でつなぐため、値型の struct では表現できません。
• 同じノードかどうかは ===（参照の同一性）で比べます。ListNode は Equatable ではないので == は使えません。
• ループ条件は fast != nil && fast?.next != nil のように、オプショナルの nil 判定で書きます。

class Solution {
    func hasCycle(_ head: ListNode?) -> Bool {
        var slow = head
        var fast = head
        while fast != nil && fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
            if slow === fast {
                return true
            }
        }
        return false
    }
}