LeetCode 141. Linked List Cycle Solution Example (Python)

LeetCode question 141. Here is an example of the answer to Linked List Cycle in Python. https://leetcode.com/problems/linked-list-cycle/

Problem overview

The problem statement is simple: Given a linked list, determine if it has a cycle in it. When a linked list is given, it has a cycle in it. The argument is a linked list.

How to solve

The algorithm for solving is simple. Here, let's consider Example 1 of the problem statement as an example. First, the graph in question (it's called a graph here because it resembles a graph as a data structure, not a graph up to high school mathematics).

Now consider slow pointer and fast pointer. The starting point here is the leftmost 3. The slow pointer advances one at a time, and the fast pointer advances two at a time. Now, if you proceed once here, it will look like the figure below.

After proceeding twice, it will be as shown in the figure below.

After proceeding 3 times, it will be as shown in the figure below.

After going three times, the slow pointer and fast pointer came to the same location (node 4).

Answer example

Below are two examples of answers.

Answer example 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

The execution result of answer example 1 is as follows. At the time of this run, it seems to be 64.54% faster than the average submission in Python3. Similarly, memory usage seems to be 100% less than that.

Answer example 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

The execution result of answer example 2 is as follows. At the time of this run, it seems to be 33.8% faster than the average submission in Python3. Similarly, memory usage seems to be 100% less than that. The reason why the processing speed is slower than the answer example 1 is thought to be that try except performs the judgment processing every time and the if statement is increased by one, so it is slower by that amount.