Алгоритм поиска цикла в связанном списке

loop_search_in_linked_list.py

from typing import Any, Optional


# Простая реализация связанного списка
class Node:
    def __init__(self, value: Any):
        self.value: Any = value
        self.next: Optional[Node] = None


class LinkedList:
    def __init__(self):
        self.head: Optional[Node] = None

    def append(self, value: Any) -> None:
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def set(self, index: int, value: Any) -> None:
        last_node = self.head
        node_index = 0
        while node_index <= index:
            if node_index == index:
                last_node.next = value
            node_index = node_index + 1
            last_node = last_node.next


def is_cycled(llist: LinkedList) -> bool:
    slow_pointer = llist.head  # Определяем указатели и назначаем им стартовую — нулевую позицию
    fast_pointer = llist.head
    # Проходим циклом по связанному списку, пока истинно условие
    while slow_pointer and fast_pointer and fast_pointer.next:
        slow_pointer = slow_pointer.next  # Скорость движения медленного указателя — одна позиция за итерацию
        fast_pointer = fast_pointer.next.next  # Скорость движения быстрого указателя — две позиции за итерацию
        if slow_pointer == fast_pointer:  # Если указатели стали равны, то есть черепаха догнала зайца
            return True  # Значит связанный список зациклен
    return False