LeetCode 141. Linked List Cycle 解答例 (Python)

LeetCodeの問題141. Linked List CycleのPythonでの解答例です。
https://leetcode.com/problems/linked-list-cycle/

問題の概要

問題文はシンプルで、連結リストが与えられている時、それがサイクル（循環）を持つかどうかを決定せよ（Given a linked list, determine if it has a cycle in it.）という問題です。
引数は連結リスト（Linked List）となっています。

解き方

解く時のアルゴリズムは単純です。ここでは例として問題文のExample 1.で考えてみましょう。
まず、問題のグラフ（高校数学までのグラフではなく、データ構造としてのグラフに似ているのでここではグラフと呼びます）です。

ここで、slow pointerとfast pointerを考えます。始点はここでは一番左の3です。slow pointerは一回につき1つ進む、fast pointerは一回につき2つ進みます。さて、ここで1回進むと、下図のようになります。

続いて2回進んだ後は下図のようになります。

3回進んだ後は下図のようになります。

この3回進んだ時点で、slow pointerとfast pointerが同じ場所（ノード4）に来ました。

解答例

以下で解答例を2つ上げます。

解答例1

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        """
        type head: ListNode
        return type: bool
        """

        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

解答例1の実行結果は以下のようになりました。この実行の時点では、Python3での提出の平均より64.54%速いようです。同様にメモリの使用量はそれより100%少ないようです。

解答例2

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        """
        type head: ListNode
        return type: bool
        """

        try:
            slow = head
            fast = head.next
            while slow != fast:
                slow = slow.next
                fast = fast.next.next
                
            return True
        except:
            return False

解答例2の実行結果は以下のようになりました。この実行の時点では、Python3での提出の平均より33.8%速いようです。同様にメモリの使用量はそれより100%少ないようです。
解答例1より処理速度が遅いのは、try exceptが毎回判定処理をしており、if文が1つ増えた形になるためその分遅くなっていることが原因と考えられます。