Метод нахождение цикла

Основные применения метода нахождение цикла:
1. Обнаружение циклов в графах или связанных структурах.
2. Проверка корректности данных.

Алгоритм:
1.    Инициализируем два указателя. Медленный указатель (slow) и быстрый указатель (fast).
2.    Начинаем обход списка. Медленный указатель перемещается на один шаг за раз, а быстрый указатель - на два шага за раз.
3.    Выставляем условие. Если цикл существует в списке, рано или поздно быстрый указатель догонит медленный указатель внутри цикла.
4.    Получаем результат. Как только быстрый и медленный указатели встретятся внутри цикла, мы знаем, что цикл существует.


Пример задачи: Проверить список на наличие цикла.

type ListNode struct {
    Value int
    Next  *ListNode
}
 
func hasCycle(head *ListNode) bool {
    if head == nil {
        return false
    }
 
    slow := head
    fast := head.Next
 
    for fast != nil && fast.Next != nil {
        if slow == fast {
            return true // Цикл обнаружен
        }
        slow = slow.Next         // Шаг fast
        fast = fast.Next.Next   // Шаг slow
    }
 
    return false // Цикл не найден
}

#ПовторяемАлгосы