LeetCode / Linked List Cycle

Kaggle繋がりでTwitterでばったりフォローした人がばったり旧知の囲碁友だった件。
ちょうど今日の問題のLinked Listのようにぐるりと回って再会しました（無理矢理

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

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

連結リストというデータ構造がお題です。
与えられた連結リストに循環構造が含まれているか（＝循環リスト）、判定する問題です。

解答・解説

解法1

はじめて連結リストというデータ構造を見た人が既存の知識で対応しようと思うと、以下のようになると思います。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

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

各要素をsetにどんどん入れていって、既にsetに入っている要素に再度出会ったら循環しているということなのでTrueを返し、そのようなことが起きずこれ以上要素がないところまでloopが回ったらFalseを返せば良いです。

解法2

解法1では空間計算量はになりますが、これを定数時間で行う方法が以下のコードです。

slowとfirstという２つのポインタを用意します。slowは1要素ずつ、firstは2要素ずつ進むポインタで、slowの1つ先にfirstを置いてスタートさせます。
すると、もし循環リストであれば、slowがリストの終端まで進む間に、firstは必ずどこかでslowに出会います。

なぜなら、slowがリストの終端まで進むnステップの間にfirstは2n進むことになりますが、firstが追いつかなければいけないslowとの距離は、最大で下図の場合でn-1なので、1要素ずつ距離を詰めるfirstはnステップの間に必ずslowに追いつけることになります。

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return False
        slow = head
        fast = head.next
        while slow is not fast:
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
        return True