Поиск начала цикла в связном списке

Поиск начала цикла в связном списке

Алгоритм Флойда (Floyd's Cycle Detection) — это гениальный алгоритм для обнаружения циклов в связных списках. Он работает без дополнительной памяти и использует только два указателя. Это одна из классических задач на интервью, проверяющая глубокое понимание алгоритмов.

Понимание алгоритма Флойда

Идея: используем два указателя с разными скоростями:

• "Черепаха" (slow) — движется на 1 шаг за раз
• "Заяц" (fast) — движется на 2 шага за раз

Если список имеет цикл, они рано или поздно встретятся внутри цикла.

Подход:
1. Оба указателя начинают с головы
2. Черепаха движется на 1 узел, заяц на 2 узла
3. Если встретились — есть цикл
4. Если заяц дошёл до None — цикла нет

Подход 1: Обнаружение цикла

Сначала проверим, есть ли вообще цикл:

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

def hasCycle(head):
    """
    Проверить наличие цикла в связном списке.
    """
    if not head or not head.next:
        return False
    
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next        # Движется на 1 шаг
        fast = fast.next.next   # Движется на 2 шага
        
        if slow == fast:  # Встретились
            return True
    
    return False

# Пример
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
head.next.next.next.next.next = head.next.next  # Цикл к узлу 3

print(hasCycle(head))  # True

Подход 2: Найти начало цикла (основная задача) ⭐

Теперь найдём точный узел, где начинается цикл:

def detectCycleStart(head):
    """
    Найти узел, с которого начинается цикл.
    
    Возвращает узел, или None если цикла нет.
    """
    if not head or not head.next:
        return None
    
    slow = head
    fast = head
    
    # Этап 1: Проверяем наличие цикла
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            # Нашли точку встречи внутри цикла
            break
    else:
        # Цикла нет
        return None
    
    # Этап 2: Найти начало цикла
    # Переместим медленный указатель в голову
    slow = head
    
    # Двигаем оба на 1 шаг
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    # Они встретятся в начале цикла
    return slow

# Пример
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
cycle_start = head.next.next  # Узел 3
head.next.next.next.next.next = cycle_start  # Цикл к узлу 3

result = detectCycleStart(head)
print(result.val)  # 3

Математическое объяснение

Почему алгоритм работает? Математика говорит:

Пусть:
- a = расстояние от головы до начала цикла
- b = расстояние от начала цикла до точки встречи
- c = остаток цикла (от точки встречи обратно к началу)

Длина цикла: L = b + c

Когда они встречаются:
- Черепаха прошла: a + b
- Заяц прошел: a + b + n*L (где n — количество полных кругов)

Так как заяц движется вдвое быстрее:
2(a + b) = a + b + n*L
a + b = n*L
a = n*L - b
a = (n-1)*L + (L - b)
a = (n-1)*L + c

Это означает:
- От головы до начала цикла = (n-1) полных циклов + расстояние c
- Если переместить медленный указатель в голову и двигать оба на 1 шаг,
  они встретятся в начале цикла после a шагов

Пошаговый пример

Пример: 1 → 2 → 3 → 4 → 5
               ↑       ↓
               └───────┘

Шаг 1 (инициализация):
slow на 1, fast на 1

Шаг 2:
slow: 1→2, fast: 1→2→3

Шаг 3:
slow: 2→3, fast: 3→4→5

Шаг 4:
slow: 3→4, fast: 5→3→4

Шаг 5:
slow: 4→5, fast: 4→5→3

Шаг 6:
slow: 5→3, fast: 3→4→5

Шаг 7:
slow: 3→4, fast: 5→3→4

Шаг 8:
slow: 4→5, fast: 4→5→3

Шаг 9:
slow: 5→3, fast: 3→4→5

Шаг 10:
slow: 3→4, fast: 5→3→4  ← Обе на узле 4

Точка встречи: узел 4

Теперь перемещаем slow в начало:
slow = head (узел 1)
fast остаётся на узле 4

Двигаем оба по одному шагу:
slow: 1→2, fast: 4→5
slow: 2→3, fast: 5→3

Они встретятся на узле 3 — начало цикла!

Полная реализация с визуализацией

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

def detectCycleStart_Full(head):
    """
    Найти узел, с которого начинается цикл.
    Алгоритм Флойда (черепаха и заяц).
    
    Args:
        head: ListNode - голова связного списка
    
    Returns:
        ListNode - узел начала цикла или None
    
    Временная сложность: O(n)
    Пространственная сложность: O(1)
    """
    if not head or not head.next:
        return None
    
    slow = head
    fast = head
    cycle_found = False
    
    # Этап 1: Поиск цикла методом Флойда
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            cycle_found = True
            break
    
    if not cycle_found:
        return None
    
    # Этап 2: Поиск начала цикла
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow

# Создание тестового списка с циклом
def create_cyclic_list():
    """
    Создать список: 1 → 2 → 3 → 4 → 5 → 3
    """
    head = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node4 = ListNode(4)
    node5 = ListNode(5)
    
    head.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5
    node5.next = node3  # Цикл
    
    return head

# Тестирование
head = create_cyclic_list()
cycle_node = detectCycleStart_Full(head)

if cycle_node:
    print(f"Цикл начинается с узла: {cycle_node.val}")  # 3
else:
    print("Цикла нет")

Альтернативный подход: HashSet O(n) память

Если дополнительная память не критична:

def detectCycleStart_HashSet(head):
    """
    Найти начало цикла используя множество.
    
    Временная сложность: O(n)
    Пространственная сложность: O(n)
    """
    visited = set()
    current = head
    
    while current:
        if current in visited:
            return current  # Нашли начало цикла
        
        visited.add(current)
        current = current.next
    
    return None  # Цикла нет

head = create_cyclic_list()
result = detectCycleStart_HashSet(head)
print(result.val)  # 3

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

Тестирование

def test_cycle_detection():
    # Тест 1: Цикл есть
    head = create_cyclic_list()
    result = detectCycleStart_Full(head)
    assert result.val == 3, "Цикл должен начинаться с узла 3"
    
    # Тест 2: Цикла нет
    head_no_cycle = ListNode(1)
    head_no_cycle.next = ListNode(2)
    head_no_cycle.next.next = ListNode(3)
    result = detectCycleStart_Full(head_no_cycle)
    assert result is None, "Цикла не должно быть"
    
    # Тест 3: Список из одного узла
    single = ListNode(1)
    result = detectCycleStart_Full(single)
    assert result is None, "Одиночный узел без цикла"
    
    # Тест 4: Цикл из одного узла (самоцикл)
    self_loop = ListNode(1)
    self_loop.next = self_loop
    result = detectCycleStart_Full(self_loop)
    assert result.val == 1, "Цикл должен быть на узле 1"
    
    print("Все тесты пройдены!")

test_cycle_detection()

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

• Обнаружение бесконечных циклов в графах и списках
• Проверка целостности структур данных
• Анализ зависимостей в системах
• Задачи безопасности — обнаружение циклических структур

Ключевые выводы

✅ Алгоритм Флойда — классическое решение O(1) памяти

✅ Два указателя с разными скоростями — мощная техника

✅ Математика — стоит за алгоритмом понимать её

✅ Для собеседования — объясняй пошагово, не заучивай