Обнаружение цикла в связном списке: разбор задачи

8 мин чтения

алгоритмы

связные списки

двойные указатели

Почему эта задача важна?

Задача на обнаружение цикла в связном списке позволяет оценить:

🧠 Понимание работы с указателями и связными структурами данных
⚡ Умение распознавать циклические структуры
🎯 Навыки оптимизации алгоритмов по памяти и времени
🐛 Способность работать с практическими проблемами в реальных системах

Постановка задачи

Формулировка:

Дан односвязный список head. Верните true, если в списке есть цикл, и false в противном случае. Цикл в связном списке существует, если хотя бы один узел может быть посещен повторно, следуя по указателю next.

Примеры:

// Первый пример ✅
Input: (head = [1, 2, 3, 4]), (index = 1)
// где index = 1 означает, что последний узел указывает на узел с индексом 1 (второй узел)
Output: true

// Второй пример ❌
Input: (head = [1]), (index = -1)
// где index = -1 означает, что цикла нет
Output: false

// Третий пример ✅
Input: (head = [1, 2]), (index = 0)
// где index = 0 означает, что последний узел указывает на узел с индексом 0 (первый узел)
Output: true

Ограничения:

Длина списка: 1 <= длина <= 1000
Значение узла: -1000 <= Node.val <= 1000
Параметр index (не передается в функцию) определяет индекс начала цикла, если он существует. Если index = -1, цикл отсутствует.

Подходы к решению

Решение 1: Метод черепахи и кролика (алгоритм Флойда) 🐢🐇

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
function hasCycle(head) {
  if (head === null || head.next === null) {
    return false
  }

  // Инициализируем двух указателей: медленного и быстрого
  let slow = head
  let fast = head

  // Двигаем указатели с разными скоростями
  while (fast !== null && fast.next !== null) {
    slow = slow.next // Черепаха движется на 1 шаг
    fast = fast.next.next // Кролик движется на 2 шага

    // Если указатели встретились, значит в списке есть цикл
    if (slow === fast) {
      return true
    }
  }

  // Если быстрый указатель достиг конца списка, цикла нет
  return false
}

Анализ решения:

✅ Оптимальная временная сложность O(n)

✅ Пространственная сложность O(1) - не требует дополнительной памяти

✅ Элегантное и классическое решение для обнаружения циклов

✅ Работает для всех типов циклов (включая самоссылки)

Решение 2: Использование множества (HashSet) 📚

function hasCycle(head) {
  // Создаем множество для отслеживания посещенных узлов
  const visited = new Set()

  // Обходим список
  let current = head
  while (current !== null) {
    // Если узел уже был в множестве, значит мы нашли цикл
    if (visited.has(current)) {
      return true
    }

    // Добавляем текущий узел в множество
    visited.add(current)

    // Переходим к следующему узлу
    current = current.next
  }

  // Если достигли конца списка, цикла нет
  return false
}

Характеристики:

✅ Простая и понятная реализация

✅ Также имеет временную сложность O(n)

❌ Пространственная сложность O(n) - требуется память для хранения множества

✅ Хорошо подходит, если важна простота реализации

Решение 3: Модификация списка (изменение указателей) 🔄

function hasCycle(head) {
  // Особый узел для маркировки посещенных узлов
  const marker = new ListNode(0)

  // Обходим список
  let current = head
  while (current !== null) {
    // Если мы уже видели этот узел, значит нашли цикл
    if (current.next === marker) {
      return true
    }

    // Запоминаем следующий узел
    const next = current.next

    // Маркируем текущий узел
    current.next = marker

    // Двигаемся дальше
    current = next
  }

  return false
}

Преимущества и недостатки:

✅ Не требует дополнительной памяти O(1)

✅ Временная сложность O(n)

❌ Изменяет исходный список (неприемлемо, если нельзя модифицировать данные)

❌ Требует восстановления списка, если необходимо сохранить его структуру

Решение 4: Обнаружение длины цикла (расширенный алгоритм Флойда) 🔍

function hasCycle(head) {
  if (head === null || head.next === null) {
    return false
  }

  // Инициализируем двух указателей
  let slow = head
  let fast = head

  // Флаг наличия цикла
  let hasCycle = false

  // Первый этап: обнаружение цикла
  while (fast !== null && fast.next !== null) {
    slow = slow.next
    fast = fast.next.next

    if (slow === fast) {
      hasCycle = true
      break
    }
  }

  // Если цикла нет, возвращаем false
  if (!hasCycle) {
    return false
  }

  // Второй этап (необязателен для данной задачи):
  // Определение начала цикла и его длины

  // Перемещаем медленный указатель в начало
  slow = head

  // Находим начало цикла
  while (slow !== fast) {
    slow = slow.next
    fast = fast.next
  }

  // Теперь slow (и fast) указывают на начало цикла
  // Можно определить длину цикла
  let cycleLength = 1
  fast = fast.next

  while (fast !== slow) {
    fast = fast.next
    cycleLength++
  }

  // Возвращаем true и, при необходимости, можно вернуть дополнительную информацию
  return true
}

Особенности:

✅ Позволяет не только обнаружить цикл, но и найти его начало и длину

✅ Пространственная сложность O(1)

✅ Полезен для более сложных задач с циклами

❌ Избыточен для простого обнаружения цикла

Распространённые ошибки

🤦‍♂️ Неправильная инициализация быстрого и медленного указателей
😅 Некорректная проверка условий завершения цикла
🐛 Пропуск проверки краевых случаев (пустой список или список с одним элементом)

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

Алгоритм Флойда (черепахи и кролика) основан на следующих принципах:

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

Докажем, что это так:

Пусть длина нециклической части списка равна a, а длина цикла равна c.
Когда черепаха вошла в цикл, кролик уже находится на расстоянии a % c от начала цикла.
Относительная скорость кролика по отношению к черепахе внутри цикла составляет 1 узел за итерацию.
Поэтому они встретятся через c - (a % c) итераций после того, как черепаха вошла в цикл.

Визуализация процесса

Рассмотрим пример списка с циклом:

1 -> 2 -> 3 -> 4 -> 5 -> 6
          ^              |
          |              v
          9 <- 8 <- 7 <-

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

Начальное состояние:
slow = 1, fast = 1

Итерация 1:
slow = 2, fast = 3

Итерация 2:
slow = 3, fast = 5

Итерация 3:
slow = 4, fast = 7

Итерация 4:
slow = 5, fast = 9

Итерация 5:
slow = 6, fast = 3

Итерация 6:
slow = 7, fast = 5

Итерация 7:
slow = 8, fast = 7

Итерация 8:
slow = 9, fast = 9 (совпадение - обнаружен цикл!)

Заключение

При решении задачи важно помнить:

🤹‍♂️ Алгоритм Флойда с двумя указателями - классический и оптимальный метод для обнаружения циклов
📊 Метод с множеством прост в реализации, но требует больше памяти
🧠 Понимание принципа работы алгоритма Флойда является важным навыком для работы с циклическими структурами

Эта задача демонстрирует элегантность алгоритмов с двумя указателями и является классическим примером, встречающимся в интервью и при разработке реальных систем, где необходимо обнаруживать и предотвращать циклы в структурах данных. 🌟