141. Linked List Cycleを解く

問題へのリンク

問題概要

連結リストheadが与えられる．
このとき，連結リストがサイクル（循環）を持つかどうかを判定する．

入力におけるposは末尾のノードと連結しているノードのインデクスを指している．
ただし，posはパラメータとして渡されない点に注意されたい．

サイクルが存在するときtrueを，そうでないときはfalseを返せ．

例：

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

制約

• 連結リストに含まれるノードの数は$[0,10^4]$
• $-10^5 \leq Node.val \leq 10^5$
• posは-1もしくは連結リストにおいて有効な整数

考えたこと

一度訪れたノードに印（visited）をつけていけばサイクルがあるか判定できると考えた．

headを前から順に見ていったとき，

• サイクルがない場合：Noneにたどり着く
• サイクルがある場合：visitedなノードに再訪問する

というように判定可能である．

以上の考え方に基づいた実装が以下である：

class Solution(object):
    def hasCycle(self, head):
        while head:
            if head.val == "#":
                return True
            head.val = "#"
            head = head.next
        return False

ただし，これでは入力が上書きされてしまう．

では，上書きを行わずに$O(n)$の空間計算量で実装するにはどうしたらよいだろうか？

アプローチを考えてみても考えつかなかったため，連結リストのサイクル検出アルゴリズムについて調べてみるとフロイドの循環検出法（英：Floyd's cycle-finding algorithm）なるものを発見した．

詳細はリンク先を読んでいただくとして，簡単に言うと連結リストを早く移動するポインタfastと遅く移動するポインタslowを用意して，

• fastがNoneになったらサイクルなし
• fast == slowとなったらサイクルあり

というように判定する方法である．

以下がフロイドの循環検出法を実装した例である：

class Solution(object):
    def hasCycle(self, head):
        if head is None:
            return False
        fast = head.next
        slow = head
        
        while fast != slow:
            if fast is None or fast.next is None:
                return False
            fast = fast.next.next
            slow = slow.next
        return True