LeetCode 142.Linked List Cycle II を解いてみる

今回は、笹平が担当です。

LeetCodeというアルゴリズムが学べるサービスがあるので、その中の問題の一つを解いてみました。
ちなみに、linked listとは日本語で連結リストと呼ばれ、要素同士がそれぞれリンク情報をもっており、繋がっています。

問題

https://leetcode.com/problems/linked-list-cycle-ii/

日本語訳

リンクされたリストが与えられた場合、サイクルが始まるノードを返します。サイクルがない場合はnullを返します。

与えられたリンクリスト内のサイクルを表現するには、リンクリスト内の末尾が接続する位置(インデックス0)を表す整数posを使用します。posが-1の場合、リンク先リストにはサイクルはありません。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func detectCycle(head *ListNode) *ListNode {
if head == nil {
return nil
}

slow := head
fast := head

for {
if fast.Next == nil || fast.Next.Next == nil {
return nil
}
slow = slow.Next
fast = fast.Next.Next

if slow == fast {
break
}
}

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

簡単にコードの説明をします。

サイクルがあるかないかの判定に、リストを移動する二つの点を作ります。(ここではslow, fastという変数を用います)
名前の通りslowは遅く、fastは速く(slowの2倍の速度で)移動します。
もし、このfastがslowに追いついたらサイクルがあるということが言えます。

Aをスタート、Bをサイクルのはじまり、Cを二つの点が重なる地点としています。

1
2
slow: x+y
fast: x+y+z+y
1
2
3
2(x+y) = x+y+z+y # fastはslowの2倍
2x+2y = x+2y+z
x=z

つまり、xとzは同じ距離になることが分かります。
これを踏まえると、A,Cからスタートして、2つの点がぶつかるところがサイクルのスタートということになります。
簡単に説明しましたが、今回の記事はこれで以上です。

次の投稿もお楽しみに!