Leetcode 141. Linked List Cycle

Problem

Linkedlistが与えられた時に、循環があるかを判断する問題になります。

Given head, the head of a linked list, determine if the linked list has a cycle in it.

InputとOutputの例は次になります。

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).

Approach #1 : Hash Table

リストが循環しているかどうかを検出するには、ノードが以前に訪れたことがあるかどうかをチェックすればよいです。自然な方法は、Hash Table (PythonではSet)を使うことで実装できます。ここで、ポイントとなるのは、Hash Tableに入れていく値はノードの参照(メモリアドレス) だということです。

class Solution:
    def hasCycle(self, head):
        nodes_seen = set()
        while head is not None:
            if head in nodes_seen:
                return True
            else:
                nodes_seen.add(head)
            head = head.next
        return False

この解法では、計算量は下記の様になります。

• Time complexity: O(n)。ここで、nはLinked Listの要素数です。各ノードは最大で一度だけ訪問されます。ハッシュセットの挿入と検索は平均的にO(1)時間であるため、全体の時間計算量はO(n)となります。
• Space complexity: O(n)。リストの各ノードをハッシュテーブルに保存する必要があるためです。リストにn個のノードがある場合、ハッシュテーブルは最大でn個のノードを保存します。

Approach #2 : Floyd's cycle-finding algorithm

Space complexityをさらに効率化できる方法があります。フロイドの循環検出アルゴリズム(Floyd's cycle-finding algorithm)を利用します。
この手法は以下のように機能します：

1. リストの先頭から開始して、遅いポインタと速いポインタを設置します。遅いポインタは各ステップで1つのノードを進み、速いポインタは2つのノードを進みます。
2. もしリストにサイクルが存在しなければ、速いポインタはいずれnull（リストの終端）に達します。
3. 一方、リストにサイクルが存在する場合、速いポインタ（2つのノードを一度に進むため）は遅いポインタを追い越し、両者はいずれ同じノードで出会うことになります。

class Solution:
    def hasCycle(self, head):
        if head is None:
            return False

        slow = head  # slow pointer
        fast = head  # fast pointer

        while fast is not None and fast.next is not None:
            slow = slow.next  # move slow pointer one step
            fast = fast.next.next  # move fast pointer two steps

            # If there is a cycle, the fast and slow pointer will meet at some node
            if slow == fast:
                return True

        # If the fast pointer reached the end of the list, there is no cycle
        return False

この解法では、計算量は下記の様になります。

• Time complexity: O(n)。Fast Pointerは、最悪の場合でもn回でSlow pointerに追いつきます。
• Space complexity: O(1)。2つのポインタのみが利用され、追加の空間をほとんど必要としません。

Reference

https://note.com/rhayahi/n/n7fc11c09fec6
https://www.youtube.com/watch?v=gBTe7lFR3vc