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

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

Описание проблемы

Нужно определить, содержит ли односвязный список цикл (loop). Цикл — это когда некоторый узел указывает на один из предыдущих узлов, создавая бесконечный путь.

Требуемые метрики:

• Временная сложность: O(n)
• Пространственная сложность: O(1)

Подход 1: Алгоритм Флойда (Черепаха и Заяц) — Оптимальный

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

def has_cycle(head):
    """
    Определяет наличие цикла в связном списке.
    Использует алгоритм Флойда (tortoise and hare).
    
    Args:
        head: ListNode - голова связного списка
    
    Returns:
        bool - True если есть цикл, False иначе
    
    Временная сложность: O(n)
    Пространственная сложность: O(1)
    """
    if not head or not head.next:
        return False
    
    slow = head      # Черепаха (движется на 1 шаг)
    fast = head      # Заяц (движется на 2 шага)
    
    while fast and fast.next:
        slow = slow.next           # Шаг 1
        fast = fast.next.next      # Шаг 2
        
        if slow == fast:           # Встретились
            return True
    
    return False

Как это работает:

• Два указателя: slow (на 1), fast (на 2 шага за раз)
• Если список не имеет цикла, fast достигнет None
• Если есть цикл, fast и slow встретятся в одном узле

Почему это работает: В цикле fast движется быстрее slow. Разница между ними уменьшается на 1 на каждом шаге. Рано или поздно они встретятся.

Подход 2: С использованием набора (Set)

def has_cycle_set(head):
    """
    Использует набор для отслеживания посещённых узлов.
    
    Временная сложность: O(n)
    Пространственная сложность: O(n)
    """
    visited = set()
    current = head
    
    while current:
        if id(current) in visited:  # Узел уже посещался
            return True
        
        visited.add(id(current))    # Добавляем узел
        current = current.next
    
    return False

Недостатки:

• Требует дополнительную память O(n)
• Медленнее из-за работы с hash-set

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

def find_cycle_start(head):
    """
    Находит узел, с которого начинается цикл.
    
    Используется модификация алгоритма Флойда:
    1. Находим точку пересечения fast и slow
    2. Переносим slow в head
    3. Движем оба на 1 шаг
    4. Место встречи — начало цикла
    """
    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
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow  # Начало цикла

Математика: Пусть расстояние от head до начала цикла = x, длина цикла = y, расстояние от начала цикла до встречи = z.

Когда fast и slow встречаются:

• slow прошёл: x + z
• fast прошёл: x + y + z (на 1 оборот больше)

Так как fast движется в 2 раза быстрее: 2(x + z) = x + y + z 2x + 2z = x + y + z x + z = y

x = y - z

То есть, расстояние от head до начала цикла равно разнице цикла и точки встречи.

Подход 4: Полная демонстрация

def analyze_cycle(head):
    """
    Полный анализ цикла в списке.
    """
    if not head:
        return {'has_cycle': False}
    
    slow = fast = head
    cycle_node = None
    
    # Находим цикл
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            cycle_node = slow
            break
    
    if not cycle_node:
        return {'has_cycle': False}
    
    # Находим начало цикла
    slow = head
    while slow != cycle_node:
        slow = slow.next
        cycle_node = cycle_node.next
    
    # Находим длину цикла
    cycle_length = 1
    temp = slow.next
    while temp != slow:
        cycle_length += 1
        temp = temp.next
    
    return {
        'has_cycle': True,
        'cycle_start': slow.val,
        'cycle_length': cycle_length
    }

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

# Тест 1: Есть цикл
head1 = ListNode(1)
head1.next = ListNode(2)
head1.next.next = ListNode(3)
head1.next.next.next = ListNode(4)
head1.next.next.next.next = head1.next  # Цикл на узел 2

print(has_cycle(head1))  # True
print(analyze_cycle(head1))
# {'has_cycle': True, 'cycle_start': 2, 'cycle_length': 3}

# Тест 2: Нет цикла
head2 = ListNode(1)
head2.next = ListNode(2)
head2.next.next = ListNode(3)
head2.next.next.next = ListNode(4)

print(has_cycle(head2))  # False
print(analyze_cycle(head2))
# {'has_cycle': False}

# Тест 3: Один узел
head3 = ListNode(1)
print(has_cycle(head3))  # False

# Тест 4: Узел указывает на себя
head4 = ListNode(1)
head4.next = head4
print(has_cycle(head4))  # True

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

Сложность алгоритма Флойда

Временная: O(n)

• В худшем случае fast может пройти 2n шагов
• slow пройдёт n шагов

Пространственная: O(1)

• Только два указателя

Граничные случаи

test_cases = [
    (None, False),                    # Пустой список
    (ListNode(1), False),            # Один узел
    (ListNode(1, ListNode(2)), False), # Два узла без цикла
]

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

• Анализ структур данных: проверка целостности связанных списков
• Поиск утечек памяти: циклические ссылки в объектах
• Обход графов: определение циклов в зависимостях
• Валидация конфигураций: проверка циклических зависимостей модулей
• Тестирование API: определение циклических редирects
• Анализ логов: поиск циклических событий и deadlocks