Как определить наличие очереди в LinkedList?

# Определение наличия цикла в LinkedList

Основная проблема

Цикл (cycle) в связном списке возникает, когда один из узлов содержит ссылку на предыдущий узел (или любой другой узел), формируя круговую ссылку. Это приводит к бесконечному циклу при итерации по списку.

Пример цикла:
Node1 → Node2 → Node3
         ↑       ↓
         ←←←←←←←←
        (ссылка вниз направлена на Node2)

Решение 1: Алгоритм Floyd (Two Pointers)

Самый популярный и эффективный метод — использование двух указателей с разной скоростью.

public class LinkedListNode {
    int value;
    LinkedListNode next;
    
    public LinkedListNode(int value) {
        this.value = value;
    }
}

public class CycleDetection {
    
    /**
     * Определяет наличие цикла в связном списке
     * Сложность: O(n), Память: O(1)
     */
    public static boolean hasCycle(LinkedListNode head) {
        if (head == null || head.next == null) {
            return false;  // Пустой список или один узел — цикла нет
        }
        
        LinkedListNode slow = head;    // Движется на 1 узел вперёд
        LinkedListNode fast = head;    // Движется на 2 узла вперёд
        
        while (fast != null && fast.next != null) {
            slow = slow.next;           // На 1 шаг
            fast = fast.next.next;      // На 2 шага
            
            if (slow == fast) {         // Указатели встретились
                return true;            // Цикл найден!
            }
        }
        
        return false;  // fast дошёл до конца — цикла нет
    }
}

// Пример использования
LinkedListNode node1 = new LinkedListNode(1);
LinkedListNode node2 = new LinkedListNode(2);
LinkedListNode node3 = new LinkedListNode(3);
LinkedListNode node4 = new LinkedListNode(4);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2;  // Цикл: 2 → 3 → 4 → 2

boolean hasCycle = CycleDetection.hasCycle(node1);
System.out.println("Has cycle: " + hasCycle);  // true

Как работает Floyd алгоритм

Ключевая идея: если в списке есть цикл, два указателя с разной скоростью обязательно встретятся внутри цикла.

Линейный список (без цикла):
head → 1 → 2 → 3 → null
slow:  ↑
fast:  ↑

Шаг 1:  slow: 1,  fast: 2
Шаг 2:  slow: 2,  fast: null → выход, нет цикла


Список с циклом:
head → 1 → 2 → 3
           ↑   ↓
           ←←←←
См slow: 1, fast: 1 (fast перепрыгнул на 2 сразу)
Шаг 1:  slow: 2, fast: 3
Шаг 2:  slow: 3, fast: 2 (fast прошёл через 3 и вернулся)
Шаг 3:  slow: 2, fast: 3
Шаг 4:  slow: 3, fast: 2
Шаг 5:  slow: 2, fast: 3
^slow и fast встретятся!

Решение 2: HashSet (поиск на основе посещения)

Используем HashSet для отслеживания посещённых узлов.

import java.util.HashSet;
import java.util.Set;

public class CycleDetectionWithSet {
    
    /**
     * Определяет цикл с использованием HashSet
     * Сложность: O(n), Память: O(n)
     */
    public static boolean hasCycle(LinkedListNode head) {
        Set<LinkedListNode> visited = new HashSet<>();
        LinkedListNode current = head;
        
        while (current != null) {
            if (visited.contains(current)) {
                return true;  // Уже посещали этот узел — есть цикл
            }
            visited.add(current);
            current = current.next;
        }
        
        return false;
    }
}

// Использование
boolean hasCycle = CycleDetectionWithSet.hasCycle(node1);  // true

Минусы HashSet подхода:

• Требует O(n) дополнительной памяти
• Медленнее, чем Floyd алгоритм

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

Временно изменяем узел для отметки посещения.

public class CycleDetectionWithMarking {
    
    /**
     * Определяет цикл с отметкой узлов
     * Сложность: O(n), Память: O(1)
     * ⚠️ Изменяет структуру списка!
     */
    public static boolean hasCycleWithMarking(LinkedListNode head) {
        LinkedListNode current = head;
        
        while (current != null) {
            if (current.value == Integer.MIN_VALUE) {
                return true;  // Отметка найдена — есть цикл
            }
            
            int originalValue = current.value;
            current.value = Integer.MIN_VALUE;  // Отмечаем узел
            current = current.next;
        }
        
        // Восстанавливаем оригинальные значения
        current = head;
        while (current != null && current.value == Integer.MIN_VALUE) {
            current.value = originalValue;
            current = current.next;
        }
        
        return false;
    }
}

Дополнительно: Найти начало цикла

Если найден цикл, можно найти узел, где он начинается.

public class CycleStartDetection {
    
    /**
     * Находит узел, который является началом цикла
     * null если цикла нет
     */
    public static LinkedListNode findCycleStart(LinkedListNode head) {
        LinkedListNode slow = head;
        LinkedListNode fast = head;
        
        // Шаг 1: Обнаружить цикл
        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;
        }
        
        // Шаг 2: Найти начало цикла
        slow = head;  // Переместить slow на head
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        
        return slow;  // slow и fast указывают на начало цикла
    }
}

// Пример
LinkedListNode cycleStart = CycleStartDetection.findCycleStart(node1);
if (cycleStart != null) {
    System.out.println("Cycle starts at node with value: " + cycleStart.value);
}

Использование в Java Collections

Для стандартного LinkedList в Java:

import java.util.LinkedList;

public class JavaLinkedListCycle {
    
    /**
     * Стандартный LinkedList не может содержать циклы,
     * так как это нарушает контракт Collection.
     * Но можно создать пользовательский класс с циклом.
     */
    
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        // Стандартный LinkedList не поддерживает циклы
        // list.get(0).next = list.get(1);  // Невозможно из-за инкапсуляции
    }
}

Сравнение методов

Реальный пример: Проверка целостности списка

@Service
public class LinkedListValidator {
    
    /**
     * Проверяет целостность пользовательского связного списка
     */
    public ValidationResult validateLinkedList(LinkedListNode head) {
        if (hasCycleFast(head)) {
            return ValidationResult.INVALID("Cycle detected in linked list");
        }
        
        if (!isProperlyTerminated(head)) {
            return ValidationResult.INVALID("List is not properly terminated");
        }
        
        return ValidationResult.VALID();
    }
    
    private boolean hasCycleFast(LinkedListNode head) {
        LinkedListNode slow = head, fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                return true;
            }
        }
        
        return false;
    }
    
    private boolean isProperlyTerminated(LinkedListNode head) {
        LinkedListNode current = head;
        int count = 0;
        final int MAX_NODES = 10000;  // Защита от бесконечного цикла
        
        while (current != null && count < MAX_NODES) {
            current = current.next;
            count++;
        }
        
        return count < MAX_NODES;  // Если count == MAX_NODES, вероятно цикл
    }
}

Вывод

Для определения наличия цикла в LinkedList используй алгоритм Floyd (Two Pointers) — он оптимален по памяти O(1) и времени O(n). Это самое частое решение на собеседованиях и в production коде.