My Algorithms Blog「141. Linked List Cycle」

Kaisei Mima — Thu, 06 Jun 2024 14:00:25 +0000

Problem

The task is to determine whether a given linked list contains a cycle. The input is provided in the following format, where each element represents a node's value in the linked list:

Input: head = [3,2,0,-4], pos = 1
Input: head = [1,2], pos = 0

If the linked list contains a cycle, the function should return True;
otherwise, it should return False. Note that the position pos where the cycle connects to the linked list is not passed as a parameter.

First approach

My initial approach uses a fast pointer and a slow pointer. The fast pointer moves two steps at a time, while the slow pointer moves one step at a time. If the fast pointer meets the slow pointer, it indicates the presence of a cycle in the linked list. However, upon reviewing my code, I believe it may be inefficient and could be optimized.

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

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False

        fast = slow = head

        while fast.next != None:
            if fast.next.next == None:
                return False
            else:
                fast = fast.next.next
                slow = slow.next
                if fast == slow:
                    return True

        return False

Time complexity: O(n)
Space complexity: O(1)

Based on the LeetCode review, which uses Floyd's Cycle Finding Algorithm, my code is shown below in comparison to the provided answer code.

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False

        slow = head
        fast = head.next

        while slow != fast:
            if fast is None or fast.next is None:
                return False
            slow = slow.next
            fast = fast.next.next
        return True

Time complexity: O(n)
Space complexity: O(1)

DEV Community: Kaisei Mima

My Algorithms Blog「141. Linked List Cycle」

Problem