Как обнаружить петлю в связанном списке?

Question

Скажем, у вас есть структура связанного списка в Java. Он состоит из узлов:

class Node {
    Node next;
    // some user data
}

и каждый узел указывает на следующий узел, за исключением последнего узла, который имеет нулевое значение для следующего. Скажем, есть вероятность, что список может содержать цикл - то есть конечный узел, вместо нуля, имеет ссылку на один из узлов в списке, который предшествовал ему.

Как лучше написать

boolean hasLoop(Node first)

, который вернул бы true, если данный узел является первым в списке с циклом, а false в противном случае? Как вы могли бы написать так, чтобы это занимало постоянное количество места и разумное количество времени?

Вот изображение того, как выглядит список с циклом:

Answer 1

Вы можете использовать алгоритм поиска цикла Флойда , также известный как алгоритм черепахи и зайца .

Идея состоит в том, чтобы иметь две ссылки на список и перемещать их с различными скоростями . Переместите один вперед на 1 узел, а другой на 2 узел.

• Если в связанном списке есть цикл, они определенно встретится.
• Еще один из две ссылки (или их next) станет null.

Java-функция, реализующая алгоритм:

boolean hasLoop(Node first) {

    if(first == null) // list does not exist..so no loop either
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer to the start of the list

    while(true) {

        slow = slow.next;          // 1 hop

        if(fast.next != null)
            fast = fast.next.next; // 2 hops
        else
            return false;          // next node null => no loop

        if(slow == null || fast == null) // if either hits null..no loop
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop
            return true;
    }
}

Answer 2

Вот уточнение решения Fast / Slow, которое правильно обрабатывает списки нечетной длины и улучшает четкость.

boolean hasLoop(Node first) {
    Node slow = first;
    Node fast = first;

    while(fast != null && fast.next != null) {
        slow = slow.next;          // 1 hop
        fast = fast.next.next;     // 2 hops 

        if(slow == fast)  // fast caught up to slow, so there is a loop
            return true;
    }
    return false;  // fast reached null, so the list terminates
}

Answer 3

Альтернативное решение для Черепахи и Кролика, не совсем хорошее, так как я временно изменяю список:

Идея состоит в том, чтобы пройти список и повернуть его вспять по ходу дела. Затем, когда вы впервые достигнете узла, который уже был посещен, его следующий указатель будет указывать «назад», вызывая повторение итерации в направлении first, где она завершается.

Node prev = null;
Node cur = first;
while (cur != null) {
    Node next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}
boolean hasCycle = prev == first && first != null && first.next != null;

// reconstruct the list
cur = prev;
prev = null;
while (cur != null) {
    Node next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}

return hasCycle;

Тестовый код:

static void assertSameOrder(Node[] nodes) {
    for (int i = 0; i < nodes.length - 1; i++) {
        assert nodes[i].next == nodes[i + 1];
    }
}

public static void main(String[] args) {
    Node[] nodes = new Node[100];
    for (int i = 0; i < nodes.length; i++) {
        nodes[i] = new Node();
    }
    for (int i = 0; i < nodes.length - 1; i++) {
        nodes[i].next = nodes[i + 1];
    }
    Node first = nodes[0];
    Node max = nodes[nodes.length - 1];

    max.next = null;
    assert !hasCycle(first);
    assertSameOrder(nodes);
    max.next = first;
    assert hasCycle(first);
    assertSameOrder(nodes);
    max.next = max;
    assert hasCycle(first);
    assertSameOrder(nodes);
    max.next = nodes[50];
    assert hasCycle(first);
    assertSameOrder(nodes);
}

Answer 4

Лучше, чем алгоритм Флойда

Ричард Брент описал альтернативный алгоритм обнаружения цикла , который во многом похож на зайца и черепаху [цикл Флойда], за исключением того, что медленный узел здесь не двигается, но позже «телепортируется» в положение быстрого узла через фиксированные интервалы.

Описание доступно здесь: http://www.siafoo.net/algorithm/11 Брент утверждает, что его алгоритм работает на 24–36% быстрее, чем алгоритм цикла Флойда. O (n) сложность времени, O (1) сложность пространства.

public static boolean hasLoop(Node root){
    if(root == null) return false;

    Node slow = root, fast = root;
    int taken = 0, limit = 2;

    while (fast.next != null) {
        fast = fast.next;
        taken++;
        if(slow == fast) return true;

        if(taken == limit){
            taken = 0;
            limit <<= 1;    // equivalent to limit *= 2;
            slow = fast;    // teleporting the turtle (to the hare's position) 
        }
    }
    return false;
}

Answer 5

черепаха и заяц

Взгляните на Алгоритм Полларда . Это не совсем та же проблема, но, возможно, вы поймете логику из нее и примените ее для связанных списков.

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

Для этого требуется только линейное время и 2 дополнительных указателя.

В Java:

boolean hasLoop( Node first ) {
    if ( first == null ) return false;

    Node turtle = first;
    Node hare = first;

    while ( hare.next != null && hare.next.next != null ) {
         turtle = turtle.next;
         hare = hare.next.next;

         if ( turtle == hare ) return true;
    }

    return false;
}

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

Answer 6

У пользователя unicornaddict есть хороший алгоритм, описанный выше, но, к сожалению, он содержит ошибку для нецикличных списков нечетной длины> = 3. Проблема в том, что fast может застрять прямо перед конец списка, slow догоняет его, и цикл (ошибочно) обнаруживается.

Вот исправленный алгоритм.

static boolean hasLoop(Node first) {

    if(first == null) // list does not exist..so no loop either.
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer to the start of the list.

    while(true) {
        slow = slow.next;          // 1 hop.
        if(fast.next == null)
            fast = null;
        else
            fast = fast.next.next; // 2 hops.

        if(fast == null) // if fast hits null..no loop.
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop.
            return true;
    }
}

Answer 7

Алгоритм

public static boolean hasCycle (LinkedList<Node> list)
{
    HashSet<Node> visited = new HashSet<Node>();

    for (Node n : list)
    {
        visited.add(n);

        if (visited.contains(n.next))
        {
            return true;
        }
    }

    return false;
}

Сложность

Time ~ O(n)
Space ~ O(n)

Answer 8

Следующий метод может быть не самым лучшим - это O (n ^ 2). Однако это должно послужить выполнению работы (в конце концов).

count_of_elements_so_far = 0;
for (each element in linked list)
{
    search for current element in first <count_of_elements_so_far>
    if found, then you have a loop
    else,count_of_elements_so_far++;
}

Answer 9

Если бы нам было разрешено встроить класс Node, я бы решил эту проблему, как я реализовал это ниже. hasLoop() выполняется за O (n) времени и занимает только пространство counter. Это кажется подходящим решением? Или есть способ сделать это без встраивания Node? (Очевидно, что в реальной реализации было бы больше методов, таких как RemoveNode(Node n) и т. Д.)

public class LinkedNodeList {
    Node first;
    Int count;

    LinkedNodeList(){
        first = null;
        count = 0;
    }

    LinkedNodeList(Node n){
        if (n.next != null){
            throw new error("must start with single node!");
        } else {
            first = n;
            count = 1;
        }
    }

    public void addNode(Node n){
        Node lookingAt = first;

        while(lookingAt.next != null){
            lookingAt = lookingAt.next;
        }

        lookingAt.next = n;
        count++;
    }

    public boolean hasLoop(){

        int counter = 0;
        Node lookingAt = first;

        while(lookingAt.next != null){
            counter++;
            if (count < counter){
                return false;
            } else {
               lookingAt = lookingAt.next;
            }
        }

        return true;

    }



    private class Node{
        Node next;
        ....
    }

}

Answer 10

public boolean hasLoop(Node start){   
   TreeSet<Node> set = new TreeSet<Node>();
   Node lookingAt = start;

   while (lookingAt.peek() != null){
       lookingAt = lookingAt.next;

       if (set.contains(lookingAt){
           return false;
        } else {
        set.put(lookingAt);
        }

        return true;
}   
// Inside our Node class:        
public Node peek(){
   return this.next;
}

Прости меня за мое невежество (я все еще довольно плохо знаком с Java и программированием), но почему вышеперечисленное не сработает?

Полагаю, это не решает проблему с постоянным пространством ... но, по крайней мере, добирается туда за разумное время, верно? Он займет только пространство связанного списка плюс пространство набора с n элементами (где n - количество элементов в связанном списке или количество элементов до тех пор, пока он не достигнет цикла). И на время анализ наихудшего случая, я думаю, предложил бы O (nlog (n)). SortedSet ищет для содержащегося () лога (n) (проверьте javadoc, но я уверен, что базовой структурой TreeSet является TreeMap, чье дерево, в свою очередь, красно-черное), и в худшем случае (без циклов или цикл в самом конце), он должен будет сделать n поиска.