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

Question

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

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

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

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

boolean hasLoop(Node first)

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

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

Answer 1

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

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

Пожалуйста, ознакомьтесь с моим постом в блоге в структуре данных связанных списков, где я также включил фрагмент кода с реализацией вышеупомянутого алгоритма на языке Java.

С уважением,

Андреас (@xnorcode)

Answer 2

Вот решение для обнаружения цикла.

public boolean hasCycle(ListNode head) {
            ListNode slow =head;
            ListNode fast =head;

            while(fast!=null && fast.next!=null){
                slow = slow.next; // slow pointer only one hop
                fast = fast.next.next; // fast pointer two hops 

                if(slow == fast)    return true; // retrun true if fast meet slow pointer
            }

            return false; // return false if fast pointer stop at end 
        }

Answer 3

Возможно, я ужасно опоздал и не справился с этой темой. Но все же ..

Почему нельзя хранить адрес узла и указанный "следующий" узел в таблице

Если бы мы могли табулировать таким образом

node present: (present node addr) (next node address)

node 1: addr1: 0x100 addr2: 0x200 ( no present node address till this point had 0x200)
node 2: addr2: 0x200 addr3: 0x300 ( no present node address till this point had 0x300)
node 3: addr3: 0x300 addr4: 0x400 ( no present node address till this point had 0x400)
node 4: addr4: 0x400 addr5: 0x500 ( no present node address till this point had 0x500)
node 5: addr5: 0x500 addr6: 0x600 ( no present node address till this point had 0x600)
node 6: addr6: 0x600 addr4: 0x400 ( ONE present node address till this point had 0x400)

Следовательно, сформирован цикл.

Answer 4

// функция поиска списка связанного списка

int findLoop(struct Node* head)
{
    struct Node* slow = head, *fast = head;
    while(slow && fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
            return 1;
    }
 return 0;
}

Answer 5

Этот подход требует много места, но его реализация проще:

Цикл можно определить, сохранив узлы на карте. И прежде чем ставить узел; проверьте, если узел уже существует. Если узел уже существует на карте, это означает, что связанный список имеет цикл.

public boolean loopDetector(Node<E> first) {  
       Node<E> t = first;  
       Map<Node<E>, Node<E>> map = new IdentityHashMap<Node<E>, Node<E>>();  
       while (t != null) {  
            if (map.containsKey(t)) {  
                 System.out.println(" duplicate Node is --" + t  
                           + " having value :" + t.data);  

                 return true;  
            } else {  
                 map.put(t, t);  
            }  
            t = t.next;  
       }  
       return false;  
  }