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つの点がぶつかるところがサイクルのスタートということになります。
簡単に説明しましたが、今回の記事はこれで以上です。

次の投稿もお楽しみに！