1

Добрый день. Задан связанный список.

class Node<T> {
   T value;
   Node<T> next;
}

Node first = new Node(1);
Node two = new Node(2);
Node third = new Node(3);
Node four = new Node(4);

first.next = two;
two.next = third;
third.next = four;
four.next = first;

Написать алгоритм определяющий, что список содержит замыкания.

boolean hasCycle(Node first);

Обратите внимание, что список может быть замкнут и в середине. К примеру, 3-й узел будет ссылаться на 2-й узел. Определение зацикленности необходимо реализовать путем прохода по узлам, без использования коллекций.

Как реализовать проверку? В интернете нашел решение, но что если цикл будет зациклен в середине. Каким образом можно это реализовать?

1
  • 1
    Тот, кто дал вам это задание, хочет проверить не вашу способность искать решения в интернете или задавать вопросы на SO, а ваше логическое мышление. 25 мар 2018 в 7:28

1 ответ 1

2

Алгоритм «черепахи и зайца» Флойда

public static boolean hasCycle(Node first) {
    Node turtle = first;
    Node hare = first;

    while (hare != null && hare.next != null) {
        tortoise = tortoise.next;
        hare = hare.next.next;
        if (tortoise == hare) {
            return true;
        }
    }
    return false;
}
1
  • Благодарю буду разбираться .
    – Terasan
    25 мар 2018 в 10:28

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.