【LeetCode】141. Linked List Cycle 解答・解説【Python】

問題
1. 原文
2. 内容
方針
解答
補足・参考・感想

問題

原文

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.

Example 1:

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

Example 2:

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.

Example 3:

Input: head = [1], pos = -1

Output: false

Explanation: There is no cycle in the linked list.

Constraints:

The number of the nodes in the list is in the range [0, 10⁴].

-10⁵ <= Node.val <= 10⁵

pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

内容

連結リストの先頭であるheadが与えられます。循環リストであるか判定してください。リスト内をポインタを継続的に追うことで再び到達できるノードがある時に循環があるといえます。内部的にはposはtailの次のポインタが指すノードのインデックスを示すために使われます。posはパラメータ(問題の入力)としては渡されません。

連結リスト内に循環があればTrue、なければFalseを返してください。

※正しくない可能性があります。

方針

・連結リスト内に循環があるかを調べるテクニックとしてスロー・ファストの2つのポインタをつかうという方法があるようです。

解答

解答1：

#O(n^2),O(n)
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = []
        #連結リストの全要素分処理する
        while head:
            #既出の要素ならTrueを返す
            if head in seen:
                return True
            #初出の要素ならSeenに加える
            seen.append(head)
            head = head.next
        #連結リストの終端にたどり着いたので循環リストではない
        return False

#O(n^2),O(n)

class Solution:

def hasCycle(self, head: Optional[ListNode]) -> bool:

seen = []

#連結リストの全要素分処理する

while head:

#既出の要素ならTrueを返す

if head in seen:

return True

#初出の要素ならSeenに加える

seen.append(head)

head = head.next

#連結リストの終端にたどり着いたので循環リストではない

return False

解答2：setを使用

#O(n),O(n)
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        #リストの代わりにsetを使う
        seen = set()
        while head:
            if head in seen:
                return True
            #setへの要素追加はadd
            seen.add(head)
            #次のノードへ
            head = head.next
        return False
#なぜhead.valではなくhead？

#O(n),O(n)

class Solution:

def hasCycle(self, head: Optional[ListNode]) -> bool:

#リストの代わりにsetを使う

seen = set()

while head:

if head in seen:

return True

#setへの要素追加はadd

seen.add(head)

#次のノードへ

head = head.next

return False

#なぜhead.valではなくhead？

解答3：2ポインタを使用

#O(n), O(1)
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        #ポインタ？
        slow = fast = head
        #連結リストの終端でない限り繰り返す
        while fast and fast.next:
            #slowは1つ進む
            slow = slow.next
            #fastは2つ進む
            fast = fast.next.next
            #slowとfastが一致したときに循環リストとわかる？
            if slow == fast:
                return True
        return False

#O(n), O(1)

class Solution:

def hasCycle(self, head: Optional[ListNode]) -> bool:

#ポインタ？

slow = fast = head

#連結リストの終端でない限り繰り返す

while fast and fast.next:

#slowは1つ進む

slow = slow.next

#fastは2つ進む

fast = fast.next.next

#slowとfastが一致したときに循環リストとわかる？

if slow == fast:

return True

return False

補足・参考・感想

参考

【データ構造】連結リスト・ランナーテクニックを解説！【頻出問題】 (suwaru.tokyo)

Linked List Cycleを理解する – Qiita

Fast and slow pointer technique in Linked List (opengenus.org)

連結リストに循環があるかを調べる方法にfast,slow pointer(tortoise and hare algorithm,フロイドの循環検出法)というテクニックがあることを知ることができた。ただ、そもそも連結リストの扱いに慣れていないので、先に連結リストについてしっかりと勉強する必要がある。

前：136. Single Number

次：217. Contains Duplicate

LeetCode 解答・解説記事一覧