Linked List Cycle Detection in Python | Floyd’s Tortoise and Hare Algorithm (LeetCode 141)

Linked List Cycle Detection using Floyd’s Algorithm (LeetCode 141)

Detecting a cycle in a singly linked list is a classic problem that can be solved efficiently using Floyd’s Tortoise and Hare algorithm.

Optimal Approach: Two Pointers (Cleaner Loop)

This is the most readable and interview-preferred implementation. It uses two pointers moving at different speeds.

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                return True

        return False
  

Alternate Implementation (Non-Cleaner Loop)

Below is a logically correct version that performs additional checks inside the loop to avoid null pointer access.

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow_pointer = fast_pointer = head
        
        while fast_pointer:
            slow_pointer = slow_pointer.next
            fast_pointer = fast_pointer.next

            if fast_pointer:
                fast_pointer = fast_pointer.next
            else:
                break

            if slow_pointer == fast_pointer:
                return True

        return False
  

Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

Full solution source code is available on GitHub: LeetCode 141 – Linked List Cycle