""" Linked List Cycle Detection Given a linked list, determine if it has a cycle using Floyd's Tortoise and Hare algorithm without extra space. Reference: https://leetcode.com/problems/linked-list-cycle/ Complexity: Time: O(n) Space: O(1) """ from __future__ import annotations class Node: def __init__(self, x: object) -> None: self.val = x self.next: Node | None = None def is_cyclic(head: Node | None) -> bool: """Determine whether a linked list contains a cycle. Args: head: Head of the linked list. Returns: True if the list has a cycle, False otherwise. Examples: >>> a = Node(1); b = Node(2); a.next = b; b.next = a >>> is_cyclic(a) True >>> c = Node(3); c.next = Node(4) >>> is_cyclic(c) False """ if not head: return False runner = head walker = head while runner.next and runner.next.next: runner = runner.next.next walker = walker.next if runner == walker: return True return False