Определить цикл в LinkedList

Определить цикл в LinkedList

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

Алгоритм Флойда: "Черепаха и заяц"

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

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

Если в списке есть цикл, эти два указателя в конце концов встретятся. Если список заканчивается (fast или fast.next становится null), цикла нет.

Структура ListNode

public class ListNode {
    int val;
    ListNode next;
    
    ListNode(int val) {
        this.val = val;
    }
}

Решение: определение наличия цикла

public class LinkedListCycle {
    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;           // Черепаха: 1 шаг
            fast = fast.next.next;      // Заяц: 2 шага
            
            if (slow == fast) {
                return true;            // Цикл найден!
            }
        }
        
        return false;                   // Цикла нет
    }
}

Пример работы

Для списка 1 → 2 → 3 → 4 → 2 → ...

На итерации 3 оба указателя указывают на узел 4, что означает наличие цикла.

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

public class LinkedListCycleDetection {
    
    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                return true;
            }
        }
        
        return false;
    }
    
    // Дополнительный метод: найти начало цикла
    public static ListNode findCycleStart(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        // Находим точку пересечения
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                break;
            }
        }
        
        // Если цикла нет
        if (fast == null || fast.next == null) {
            return null;
        }
        
        // Находим начало цикла
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        
        return slow;
    }
    
    public static void main(String[] args) {
        // Тест 1: Цикл существует
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2;  // Цикл: 4 → 2
        
        System.out.println(hasCycle(node1)); // true
        System.out.println(findCycleStart(node1).val); // 2
        
        // Тест 2: Цикла нет
        ListNode nodeA = new ListNode(1);
        ListNode nodeB = new ListNode(2);
        ListNode nodeC = new ListNode(3);
        
        nodeA.next = nodeB;
        nodeB.next = nodeC;
        nodeC.next = null;
        
        System.out.println(hasCycle(nodeA)); // false
    }
}

Почему алгоритм Флойда работает?

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

Предположим цикл существует. Пусть:

• a — расстояние от начала списка до начала цикла
• b — расстояние от начала цикла до точки встречи
• c — длина цикла

Когда slow делает n шагов, fast делает 2n шагов. Они встретятся, когда:

• slow находится в цикле: n = a + b
• fast в цикле дважды прошёл расстояние slow: 2n = a + b + k*c

Отсюда: n = k*c, что гарантирует встречу.

Анализ сложности

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

• В худшем случае оба указателя проходят весь список
• Fast указатель может сделать максимум n/2 итераций

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

• Используем только два указателя
• Не выделяем дополнительную память
• Не модифицируем список

Преимущества перед другими подходами

Вопросы на собеседовании

1. Почему fast движется на 2 шага? — чтобы гарантировать встречу в цикле
2. Найти начало цикла — используя двойной проход (см. код выше)
3. Длина цикла — после встречи, считаем шаги до повторной встречи