Определение цикла в связном списке

Цикл в связном списке: Алгоритм "Черепахи и зайца"

Понимание задачи

Нужно определить, есть ли цикл (цикличная связность) в связном списке. Это классическая задача с несколькими решениями, но оптимальное использует два указателя с разной скоростью.

Структура связного списка

class ListNode:
    def __init__(self, val: int = 0, next=None):
        self.val = val
        self.next = next

Решение 1: "Черепаха и заяц" (Two Pointers) O(n)

def has_cycle(head: ListNode) -> bool:
    """
    Определяет наличие цикла используя два указателя.
    Заяц движется в 2 раза быстрее черепахи.
    
    Если есть цикл, они встретятся.
    Если нет цикла, заяц дойдёт до None.
    
    Args:
        head: Начало связного списка
    
    Returns:
        True если есть цикл, иначе False
    """
    if not head or not head.next:
        return False
    
    slow = head      # Черепаха
    fast = head      # Заяц
    
    while fast and fast.next:
        slow = slow.next          # Черепаха: один шаг
        fast = fast.next.next     # Заяц: два шага
        
        if slow == fast:  # Они встретились - есть цикл!
            return True
    
    return False  # Достигли конца списка - нет цикла

Почему это работает?

Если есть цикл, оба указателя войдут в него. Заяц движется быстрее, поэтому он "обгонит" черепаху и они встретятся внутри цикла.

Математическое доказательство:

• Если есть цикл длины C
• Расстояние между slow и fast сокращается на 1 за каждый шаг
• Когда fast догонит slow, они встретятся
• Максимум это произойдёт после O(n) шагов

Пример:

Список: 1 → 2 → 3 → 4
                ↑   ↓
                └───┘

Шаг 0: slow=1, fast=1
Шаг 1: slow=2, fast=3
Шаг 2: slow=3, fast=2  (fast обошёл вокруг)
Шаг 3: slow=4, fast=4  (ВСТРЕТИЛИСЬ!)

Возвращаем True ✓

Сложность:

• Время: O(n) - в худшем случае пройдём весь список
• Память: O(1) - используем только два указателя

Решение 2: Множество (HashSet) O(n) - простое

def has_cycle_hashset(head: ListNode) -> bool:
    """Простой способ: сохраняем посещённые узлы."""
    visited = set()
    current = head
    
    while current:
        if current in visited:  # Уже видели этот узел
            return True
        visited.add(current)
        current = current.next
    
    return False

Плюсы: Просто понять и реализовать
Минусы: O(n) память (плохо для больших списков)

Решение 3: Нахождение начала цикла

def detect_cycle_start(head: ListNode) -> ListNode:
    """
    Находит узел, с которого начинается цикл.
    
    Используем свойство: если есть цикл,
    то расстояние от head до начала цикла
    = расстояние между slow и началом цикла
    при встречи slow и fast.
    """
    if not head or not head.next:
        return None
    
    slow = head
    fast = head
    
    # Находим точку встречи (проверяем есть ли цикл)
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:  # Обнаружили цикл
            # Теперь находим начало цикла
            # Движем slow от head, fast от точки встречи
            # Они встретятся в начале цикла
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            
            return slow  # Начало цикла найдено
    
    return None  # Нет цикла

Математика: Если расстояние от head до начала цикла = x, а от начала цикла до точки встречи = y, то длина цикла = L. Тогда x = L - y, поэтому оба указателя встретятся в начале цикла.

Тесты

def test_has_cycle():
    # Случай 1: Нет цикла
    # 1 → 2 → 3 → None
    node1 = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node1.next = node2
    node2.next = node3
    
    assert has_cycle(node1) == False
    
    # Случай 2: Есть цикл
    # 1 → 2 → 3
    #     ↑   ↓
    #     └───┘
    node4 = ListNode(1)
    node5 = ListNode(2)
    node6 = ListNode(3)
    node4.next = node5
    node5.next = node6
    node6.next = node5  # Цикл!
    
    assert has_cycle(node4) == True
    
    # Случай 3: Цикл на самом себе
    node7 = ListNode(1)
    node7.next = node7
    
    assert has_cycle(node7) == True
    
    # Случай 4: Пустой список
    assert has_cycle(None) == False
    
    # Случай 5: Один элемент без цикла
    node8 = ListNode(1)
    assert has_cycle(node8) == False
    
    print("Все тесты пройдены!")

Сравнение подходов

Интересные вопросы для интервью

Q: Почему Fast движется в 2 раза быстрее?
A: Любой коэффициент > 1 работает (3x, 10x). Но 2x - оптимальный для простоты.

Q: Будут ли они всегда встречаться?
A: Да, если есть цикл. Относительная скорость = 1 шаг/итерация, циклическое расстояние конечно.

Q: Где они встретятся?
A: Внутри цикла, но не обязательно в начале. Используй второй проход для начала.

Практическое применение

• Обнаружение deadlock-ов (циклических зависимостей)
• Проверка корректности графовых структур
• Валидация связных списков в garbage collector