Как определить цикл в связанном списке?

Ответ 1

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

 Идея состоит в том, чтобы иметь две ссылки на список и перемещать их на разные скорости. Переместите один вперед на 1 node, а другой - на узлы 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;
    }
}

Ответ 2

Здесь уточняется быстрое или медленное решение, которое правильно обрабатывает списки нечетной длины и улучшает четкость.

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
}

Ответ 3

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

Идея состоит в том, чтобы пройти список и отменить его, когда вы идете. Затем, когда вы впервые дойдете до node, который уже был посещен, его следующий указатель будет указывать "назад", в результате чего итерация снова продолжит к 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);
}

Ответ 4

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

Описание доступно здесь: http://www.siafoo.net/algorithm/11 Брент утверждает, что его алгоритм на 24-36% быстрее, чем алгоритм цикла Floyd. 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 position) 
        }
    }
    return false;
}

Ответ 5

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

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

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

Для этого требуется только линейное время и 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 для нулей. Кроме того, поскольку черепаха всегда позади, вам не нужно проверять ее на нуль - заяц сделал это уже. )

Ответ 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;
    }
}

Ответ 7

Ниже может быть не лучший метод - это 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++;
}

Ответ 8

Алгоритм

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)

Ответ 9

Вы также можете посмотреть алгоритм Nivasch: алгоритм Ниваша.

Или вы можете проверить персональную страницу Gabriel Nivasch на алгоритм стека для определения цикла, который также содержит реализацию алгоритма C.

Ответ 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)). Сортированные запросы для contains() - это log (n) (проверьте javadoc, но я уверен, что базовая структура TreeSet - TreeMap, в свою очередь это красно-черное дерево), а в худшем случае (без циклов, или цикл в самом конце), он должен будет выполнять n поисков.

Ответ 11

Если нам разрешено вставлять класс 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;
        ....
    }

}

Ответ 12

Вы могли бы даже сделать это в постоянное время O (1) (хотя это было бы не очень быстро или эффективно): существует ограниченное количество узлов, которые может хранить ваша память компьютера, например N записей. Если вы пересекаете более N записей, тогда у вас есть цикл.

Ответ 13

 // To detect whether a circular loop exists in a linked list
public boolean findCircularLoop() {
    Node slower, faster;
    slower = head;
    faster = head.next; // start faster one node ahead
    while (true) {

        // if the faster pointer encounters a NULL element
        if (faster == null || faster.next == null)
            return false;
        // if faster pointer ever equals slower or faster next
        // pointer is ever equal to slower then it a circular list
        else if (slower == faster || slower == faster.next)
            return true;
        else {
            // advance the pointers
            slower = slower.next;
            faster = faster.next.next;
        }
    }
}

Ответ 14

Я не вижу никакого способа сделать это фиксированным количеством времени или пространства, оба будут увеличиваться с размером списка.

Я бы использовал IdentityHashMap (учитывая, что еще не существует IdentityHashSet) и сохраните каждый Node в карте. Перед сохранением Node вы вызываете containsKey на нем. Если Node уже существует, у вас есть цикл.

ItentityHashMap использует == вместо .equals, чтобы вы проверяли, где находится объект в памяти, а не в том же содержимом.

Ответ 15

Обнаружение цикла в связанном списке может быть выполнено одним из самых простых способов, что приводит к сложности O (N).

По мере прохождения списка, начиная с главы, создайте отсортированный список адресов. Когда вы вставляете новый адрес, проверьте, есть ли адрес в отсортированном списке, который выполняет сложность O (logN).

Ответ 16

Мне может быть очень поздно и новичок в этой теме. Но все же..

Почему не удастся сохранить адрес node и указатель "next" node в таблице

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

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)

Следовательно, образуется цикл.

Ответ 17

Вот мой исполняемый код.

То, что я сделал, состоит в том, чтобы почитать связанный список, используя три временных узла (сложность пространства O(1)), которые отслеживают ссылки.

Интересный факт об этом заключается в том, чтобы помочь обнаружить цикл в связанном списке, потому что, когда вы продвигаетесь вперед, вы не ожидаете вернуться к исходной точке (root node), а один из временных узлов должен перейдите к null, если у вас нет цикла, что означает, что он указывает на корень node.

Временная сложность этого алгоритма O(n), а сложность пространства O(1).

Ниже приведен класс node для связанного списка:

public class LinkedNode{
    public LinkedNode next;
}

Вот основной код с простым тестовым примером из трех узлов, который последний node указывает на второй node:

    public static boolean checkLoopInLinkedList(LinkedNode root){

        if (root == null || root.next == null) return false;

        LinkedNode current1 = root, current2 = root.next, current3 = root.next.next;
        root.next = null;
        current2.next = current1;

        while(current3 != null){
            if(current3 == root) return true;

            current1 = current2;
            current2 = current3;
            current3 = current3.next;

            current2.next = current1;
        }
        return false;
    }

Ниже приведен простой пример трех узлов: последний node, указывающий на второй node:

public class questions{
    public static void main(String [] args){

        LinkedNode n1 = new LinkedNode();
        LinkedNode n2 = new LinkedNode();
        LinkedNode n3 = new LinkedNode();
        n1.next = n2;
        n2.next = n3;
        n3.next = n2;

        System.out.print(checkLoopInLinkedList(n1));
    }
}

Ответ 18

Этот код оптимизирован и приведет к результату быстрее, чем к выбранному в качестве наилучшего ответа. Этот код экономит от перехода на очень длительный процесс преследования указателя вперед и назад node, который будет возникать в следующем случае, если мы следуем методу "наилучшего ответа". Посмотрите на сухой пробег следующего, и вы поймете, что я пытаюсь сказать. Затем посмотрите на проблему с помощью приведенного ниже метода и измерьте "нет". шагов, предпринятых для поиска ответа.

1- > 2- > 9- > 3 ^ -------- ^

Вот код:

boolean loop(node *head)
{
 node *back=head;
 node *front=head;

 while(front && front->next)
 {
  front=front->next->next;
  if(back==front)
  return true;
  else
  back=back->next;
 }
return false
}

Ответ 19

boolean hasCycle(Node head) {

    boolean dec = false;
    Node first = head;
    Node sec = head;
    while(first != null && sec != null)
    {
        first = first.next;
        sec = sec.next.next;
        if(first == sec )
        {
            dec = true;
            break;
        }

    }
        return dec;
}

Используйте вышеприведенную функцию для обнаружения цикла в связанном списке в java.

Ответ 20

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

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

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

С Уважением,

Андреас (@xnorcode)

Ответ 21

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

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 
        }

Ответ 22

public boolean isCircular() {

    if (head == null)
        return false;

    Node temp1 = head;
    Node temp2 = head;

    try {
        while (temp2.next != null) {

            temp2 = temp2.next.next.next;
            temp1 = temp1.next;

            if (temp1 == temp2 || temp1 == temp2.next) 
                return true;    

        }
    } catch (NullPointerException ex) {
        return false;

    }

    return false;

}

Ответ 23

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

Петля может быть идентифицирована путем хранения узлов на карте. И перед тем, как поставить node; проверьте, существует ли node. Если node уже существует в карте, это означает, что Linked List имеет цикл.

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;  
  }  

Ответ 24

Вот мое решение в java

boolean detectLoop(Node head){
    Node fastRunner = head;
    Node slowRunner = head;
    while(fastRunner != null && slowRunner !=null && fastRunner.next != null){
        fastRunner = fastRunner.next.next;
        slowRunner = slowRunner.next;
        if(fastRunner == slowRunner){
            return true;
        }
    }
    return false;
}