LeetCode - Linked List Cycle をSwiftで解説する

• 元の問題は英語なので、代わりに翻訳したものを記載しています。
• 回答はあくまでも例であり、他の方法も存在します。

前置き

Swiftで連結リストについて学びたい人にとっては程よい問題かと思います。
（ListNodeの概念が頭に入っていないと、すんなり入ってこないかもしれません）

Linked List（連結リスト）とは

- データ構造の1つであり、他のデータ構造の実装に使われる。
- 一連のノードが、任意のデータフィールド群を持ち、1つか2つの参照（リンク）により次（および前）のノードを指している。

ざっくり要約すると
「あるクラスがあって、それは自分の次or前のクラスの情報を保持しており参照されたリスト」
になっているという感じです。

[example]

図にするともう少しわかりやすいかと思います。

あるクラスが「数字」と「次のクラスの情報」を持っているとします。
その場合、以下のようになります。

これがLinked Listになります。

[ListNode]

Linked ListでつながっているクラスのことをNode（ノード）という言い方をします。
javaなどではimportすれば使えたりするのですが、Swiftでは用意されていません。

なので、LeetCode上では以下のように定義されています。
（LeetCodeに限らず、一般的にだいたいこんな感じだと思います。）

public class ListNode {
    public var val: Int // 自信が持つ値
    public var next: ListNode? // 次のノードの情報
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

これを前提に問題を進めていきます。

問題

問題	難易度
141. Linked List Cycle	easy

あるLinked Listがあり、その先頭のhead（ノード）が与えられた場合、サイクルがあるかどうかを判断します。

連続的にたどることで再び到達できるノードがある場合、サイクルがあると言えます。
内部的に「pos」は次の接続されているノードのインデックスを表すために使用されます。
「pos」はパラメータとして渡されないことに注意してください。

Linked Listにサイクルがある場合はtrueを返します。
そうでなければ、falseを返します。

補足として、以下のようなtrueを返すテストケースが与えられます。

Input: head = [3,2,0,-4], pos = 1

３から始まるLinked Listで、サイクルの接続先（pos）は２番目を表しています。
（配列で考えるので０から始まると考えると、pos=１は２番目の２になる）

図だとこのようになります

つまり、ノードがサイクルしている（Linked List）であることを調べるには、
posで指定された値が 0 <= pos < リストのカウント であれば良いことになります。

答え

２つの方法を提示します。

1. Hash Table（ハッシュテーブル）

Hash TableはKeyとValueの組み合わせをもつデータ構造の１つで、一般的にハッシュテーブルやハッシュマップと呼ばれます。要素の挿入・削除・検索をほぼ O(1) で行うことができるため、競技プログラミングではよく使われるものです。

SwiftではHash Tableという名前ではなく Dictionary という形で表現されています。

func hasCycle(_ head: ListNode?) -> Bool {
    // Hash Tableを定義。また、引数headのままだと加工ができないので、別の変数にいれている。
    var hashTable = [Int: Int](), current = head
    
    // ノードから値を１つず取り出して見る
    while let c = current {
        // ハッシュ値があればサイクルしていると判断できる
        if let val = hashTable[c.val], val == c.next?.val {
            return true
	// ハッシュ値がなければ、値を追加
        } else if let n = c.next {
            hashTable[c.val] = n.val
 	// サイクルがない場合
	} else {
            return false
        }
        current = c.next
    }
    // なくても良いがコンパイルエラーになるので記載
    return false
}

ノードから値を取り出していき、１つずつ保存していきます。

探索しつつ再び保存した値にたどり着いた時、それは 既に通った道(Node) であり、サイクルしていると考えられます。逆に見つからなければ、サイクルしていないということになります。

2. Two Pointers

名前の通り２点（同時に２通りの探索をするもの）を使用して解いていく方法です。
（尺取り法のことをTwo Pointersとも言いますが今回は違います）

方法としては、全探索では時間がかかってしまうので、

1. 普通にNodeを探索
2. 倍速で次のNodeを探索

この２点を用意します。

ともあれ、実装はこんな感じです。

func hasCycle(_ head: ListNode?) -> Bool {
    var slow = head // 通常の探索用
    var fast = slow?.next // 倍速の探索用

    while let s = slow, let f = fast {
        // 一致しているものがあればサイクルしていると判断できる
        if s === f {
            return true
        }
        slow = s.next // 次の探索を行うためにセット
        fast = f.next?.next // 次の次の探索を行うためにセット
    }

    return false
}

もしサイクルしているのであれば、倍速の探索はサイクルして最初（posの値）からに戻るので、いずれ通常の探索に追いつくはずです。

イメージとしては、池の周りを足の「速い人」と「遅い人」が同時に走るとします。
いずれは「速い人」が１周して「遅い人」に追いつくのを想像するとわかりやすいかと思います。

つまり、
追いついた = サイクルしている = Linked Listである
ということが言えます。

実行結果

Kind	Runtime	Memory
① Hash Table	52ms~	22MB前後
② Two Pointers	40ms~	15MB前後

引用

• Wikipedia - 連結リスト
• LeetCode - Solution