LeetCode 141. Linked List Cycle
はじめに
LeetCode 「141. Linked List Cycle」の問題をGoで解きました。
問題
問題文
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
和訳
リンクリストの先頭であるheadが与えられたら、そのリンクリストにサイクルがあるかどうかを判定する。
リンクリストにサイクルがあるのは、リスト内に次のポインタをたどり続けることで再び到達できるノードがある場合である。内部的には、posはtailの次のポインタが接続されているノードのインデックスを表すのに使われる。 posはパラメータとして渡されないことに注意。
リンクリストにサイクルがあればtrueを返す。そうでない場合はfalseを返す。
例
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
制約
- The number of the nodes in the list is in the range [0, 104].
- -105 <= Node.val <= 105
- pos is -1 or a valid index in the linked-list.
問題の理解
サイクルとは、リンクリストのどこかのノードが、前に登場したノードをnext経由で指してしまう状態です。
つまりnextをたどっていくと、どこかで永遠にループする構造です。
posとはテストケースと内部的に構築するための情報です。
- pos = -1 → サイクルなし（ 最後のノード（tail）はどこにも繋がっていない）
- pos >= 0 → サイクルあり（ 最後のノードの next が、リスト中の「pos番目のノード」を指している）
解答
ループしているか確認する方法としては、Floydの循環検出アルゴリズム がよく使われるようです。
簡単に説明します。
2つのポインタを用意します。
- 速いポインタ=
fast：1回で2つ進む - 遅いポインタ=
slow：1回で1つ進む
サイクルがなければfastがnilに到達し、サイクルがあればが回ってslowに追いつきます。
fastはslowよりも1つ多く進むため、ループがある場合には、fastはslowに1つずつ近づくことになり、必ず重なる場所が現れます。
コード
func hasCycle(head *ListNode) bool {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
return true
}
}
return false
}
計算量
- 時間的計算量：O(n)
- 空間的計算量：O(1)
Discussion