floyd s cycle detection algorithm is a popular algorithm used to detect cycles in a linked list it uses two pointers a slow pointer and a fast pointer to traverse the linked list the slow pointer moves one node at a time while the fast pointer moves two nodes at a time if there is a cycle in the linked list the fast pointer will eventually catch up to the slow pointer and they will meet at the same node if there is no cycle the fast pointer will reach the end of the linked list and the algorithm will terminate for more information https en wikipedia orgwikicycledetectionfloyd stortoiseandhare a class representing a node in a singly linked list a class representing a singly linked list iterates through the linked list returns iterator an iterator over the linked list examples linkedlist linkedlist listlinkedlist linkedlist addnode1 tuplelinkedlist 1 avoid infinite loop in there s a cycle adds a new node to the end of the linked list args data any the data to be stored in the new node examples linkedlist linkedlist linkedlist addnode1 linkedlist addnode2 linkedlist addnode3 linkedlist addnode4 tuplelinkedlist 1 2 3 4 detects if there is a cycle in the linked list using floyd s cycle detection algorithm returns bool true if there is a cycle false otherwise examples linkedlist linkedlist linkedlist addnode1 linkedlist addnode2 linkedlist addnode3 linkedlist addnode4 linkedlist detectcycle false create a cycle in the linked list linkedlist head nextnode nextnode nextnode linkedlist head nextnode linkedlist detectcycle true create a cycle in the linked list it first checks if the head nextnode and nextnode nextnode attributes of the linked list are not none to avoid any potential type errors a class representing a node in a singly linked list a class representing a singly linked list iterates through the linked list returns iterator an iterator over the linked list examples linked_list linkedlist list linked_list linked_list add_node 1 tuple linked_list 1 avoid infinite loop in there s a cycle adds a new node to the end of the linked list args data any the data to be stored in the new node examples linked_list linkedlist linked_list add_node 1 linked_list add_node 2 linked_list add_node 3 linked_list add_node 4 tuple linked_list 1 2 3 4 detects if there is a cycle in the linked list using floyd s cycle detection algorithm returns bool true if there is a cycle false otherwise examples linked_list linkedlist linked_list add_node 1 linked_list add_node 2 linked_list add_node 3 linked_list add_node 4 linked_list detect_cycle false create a cycle in the linked list linked_list head next_node next_node next_node linked_list head next_node linked_list detect_cycle true create a cycle in the linked list it first checks if the head next_node and next_node next_node attributes of the linked list are not none to avoid any potential type errors output true
from collections.abc import Iterator
from dataclasses import dataclass
from typing import Any, Self


@dataclass
class Node:
    

    data: Any
    next_node: Self | None = None


@dataclass
class LinkedList:
    

    head: Node | None = None

    def __iter__(self) -> Iterator:
        
        visited = []
        node = self.head
        while node:
            
            if node in visited:
                return
            visited.append(node)
            yield node.data
            node = node.next_node

    def add_node(self, data: Any) -> None:
        
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            return

        current_node = self.head
        while current_node.next_node is not None:
            current_node = current_node.next_node

        current_node.next_node = new_node

    def detect_cycle(self) -> bool:
        
        if self.head is None:
            return False

        slow_pointer: Node | None = self.head
        fast_pointer: Node | None = self.head

        while fast_pointer is not None and fast_pointer.next_node is not None:
            slow_pointer = slow_pointer.next_node if slow_pointer else None
            fast_pointer = fast_pointer.next_node.next_node
            if slow_pointer == fast_pointer:
                return True

        return False


if __name__ == "__main__":
    import doctest

    doctest.testmod()

    linked_list = LinkedList()
    linked_list.add_node(1)
    linked_list.add_node(2)
    linked_list.add_node(3)
    linked_list.add_node(4)

    
    
    
    if (
        linked_list.head
        and linked_list.head.next_node
        and linked_list.head.next_node.next_node
    ):
        linked_list.head.next_node.next_node.next_node = linked_list.head.next_node

    has_cycle = linked_list.detect_cycle()
    print(has_cycle)