Como detectar um loop em uma lista vinculada?

Digamos que você tenha uma estrutura de lista vinculada em Java. É composto de nós:

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

e cada Nó aponta para o próximo nó, exceto o último Nó, que é nulo para o próximo. Digamos que exista a possibilidade de a lista conter um loop - ou seja, o Nó final, em vez de ter um nulo, tem uma referência a um dos nós da lista que vieram antes dela.

Qual é a melhor maneira de escrever

boolean hasLoop(Node first)

que retornaria truese o nó fornecido fosse o primeiro de uma lista com um loop e falsecaso contrário? Como você pode escrever para ocupar uma quantidade constante de espaço e uma quantidade razoável de tempo?

Aqui está uma imagem de como é uma lista com um loop:

Você pode usar o algoritmo de descoberta de ciclo de Floyd , também conhecido como algoritmo de tartaruga e lebre .

A idéia é ter duas referências à lista e movê-las em velocidades diferentes . Avance um por 1nó e o outro por 2nós.

• Se a lista vinculada tiver um loop, eles definitivamente se encontrarão.
• Caso contrário, qualquer uma das duas referências (ou as suas next) se tornará null.

Função Java que implementa o algoritmo:

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

Aqui está um refinamento da solução Fast / Slow, que lida corretamente com listas de tamanhos ímpares e melhora a clareza.

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
}

Melhor que o algoritmo de Floyd

Richard Brent descreveu um algoritmo de detecção de ciclo alternativo , que é muito parecido com a lebre e a tartaruga [ciclo de Floyd], exceto que o nó lento aqui não se move, mas depois é "teleportado" para a posição do nó rápido no ponto fixo. intervalos.

A descrição está disponível aqui: http://www.siafoo.net/algorithm/11 Brent afirma que seu algoritmo é 24 a 36% mais rápido que o algoritmo de ciclo de Floyd. O (n) complexidade do tempo, O (1) complexidade do espaço.

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

Uma solução alternativa para a tartaruga e o coelho, não tão agradável quanto eu altero temporariamente a lista:

A idéia é percorrer a lista e inverter a medida que você avança. Então, quando você alcançar um nó que já foi visitado pela primeira vez, seu próximo ponteiro apontará "para trás", fazendo com que a iteração prossiga firstnovamente, onde termina.

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;

Código do teste:

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

Tartaruga e lebre

Dê uma olhada no algoritmo rho de Pollard . Não é exatamente o mesmo problema, mas talvez você entenda a lógica e a aplique em listas vinculadas.

(se você é preguiçoso, basta verificar a detecção de ciclo - verifique a parte sobre a tartaruga e a lebre.)

Isso requer apenas tempo linear e 2 indicadores extras.

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

(A maioria da solução não verifica os dois nexte os next.nextnulos. Além disso, como a tartaruga está sempre atrasada, você não precisa verificar se é nulo - a lebre já fez isso.)

O usuário unicornaddict possui um bom algoritmo acima, mas, infelizmente, contém um erro para listas não-loops de comprimento estranho> = 3. O problema é que ele fastpode "ficar preso" pouco antes do final da lista, slowalcançá-lo e um loop é (erroneamente) detectado.

Aqui está o algoritmo corrigido.

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

Nesse contexto, existem muitos materiais textuais em todos os lugares. Eu só queria postar uma representação diagramática que realmente me ajudou a entender o conceito.

Quando rápido e lento se encontram no ponto p,

Distância percorrida rapidamente = a + b + c + b = a + 2b + c

Distância percorrida lentamente = a + b

Como o jejum é 2 vezes mais rápido que o lento. Então a + 2b + c = 2 (a + b) , então obtemos a = c .

Portanto, quando outro ponteiro lento é executado novamente da cabeça para q , ao mesmo tempo, o ponteiro rápido é executado de p para q , então eles se encontram no ponto q juntos.

public ListNode detectCycle(ListNode head) {
    if(head == null || head.next==null)
        return null;

    ListNode slow = head;
    ListNode fast = head;

    while (fast!=null && fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;

        /*
        if the 2 pointers meet, then the 
        dist from the meeting pt to start of loop 
        equals
        dist from head to start of loop
        */
        if (fast == slow){ //loop found
            slow = head;
            while(slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }            
    }
    return null;
}

Algoritmo

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

Complexidade

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

O seguinte pode não ser o melhor método - é O (n ^ 2). No entanto, deve servir para fazer o trabalho (eventualmente).

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

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

Perdoe minha ignorância (ainda sou relativamente novo em Java e programação), mas por que as opções acima não funcionavam?

Eu acho que isso não resolve o problema constante de espaço ... mas pelo menos chega lá em um tempo razoável, correto? Ele ocupará apenas o espaço da lista vinculada mais o espaço de um conjunto com n elementos (em que n é o número de elementos na lista vinculada ou o número de elementos até que ele atinja um loop). E, por algum tempo, a análise do pior caso, eu acho, sugeriria O (nlog (n)). As pesquisas SortedSet para contains () são log (n) (verifique o javadoc, mas tenho certeza de que a estrutura subjacente do TreeSet é o TreeMap, que por sua vez é uma árvore vermelha e preta) e, na pior das hipóteses (sem loops, ou loop no final), ele terá que fazer n pesquisas.

Se for permitido incorporar a classe Node, eu resolveria o problema como o implementei abaixo. hasLoop()roda em O (n) tempo e ocupa apenas o espaço de counter. Parece uma solução apropriada? Ou existe uma maneira de fazer isso sem incorporar Node? (Obviamente, em uma implementação real, haveria mais métodos, como RemoveNode(Node n)etc.)

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

}

Você pode até fazer isso em tempo O (1) constante (embora não seja muito rápido ou eficiente): existe uma quantidade limitada de nós que a memória do computador pode conter, digamos, N registros. Se você percorrer mais de N registros, terá um loop.

 // 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's next
        // pointer is ever equal to slower then it's a circular list
        else if (slower == faster || slower == faster.next)
            return true;
        else {
            // advance the pointers
            slower = slower.next;
            faster = faster.next.next;
        }
    }
}

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

Use a função acima para detectar um loop na lista vinculada em java.

A detecção de um loop em uma lista vinculada pode ser feita de uma das maneiras mais simples, o que resulta na complexidade de O (N) usando hashmap ou O (NlogN) usando uma abordagem baseada em classificação.

À medida que você percorre a lista começando do início, crie uma lista classificada de endereços. Ao inserir um novo endereço, verifique se o endereço já existe na lista classificada, o que exige complexidade O (logN).

Não vejo nenhuma maneira de fazer isso levar uma quantidade fixa de tempo ou espaço; ambos aumentarão com o tamanho da lista.

Eu usaria um IdentityHashMap (já que ainda não há um IdentityHashSet) e armazenaria cada Nó no mapa. Antes de um nó ser armazenado, você chamaria containsKey nele. Se o nó já existir, você terá um ciclo.

O ItentityHashMap usa == em vez de .equals, para que você verifique onde o objeto está na memória e não se ele possui o mesmo conteúdo.

Eu posso estar terrivelmente atrasado e novo para lidar com esse tópico. Mas ainda..

Por que o endereço do nó e o nó "próximo" apontado não podem ser armazenados em uma tabela

Se pudéssemos tabular dessa maneira

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)

Portanto, há um ciclo formado.

Aqui está o meu código executável.

O que fiz foi reverenciar a lista vinculada usando três nós temporários (complexidade do espaço O(1)) que controlam os links.

O fato interessante de fazer isso é ajudar a detectar o ciclo na lista vinculada, pois à medida que você avança, não espera voltar ao ponto inicial (nó raiz) e um dos nós temporários deve ir para nulo, a menos que tem um ciclo, o que significa que aponta para o nó raiz.

A complexidade do tempo deste algoritmo é O(n)e a complexidade do espaço é O(1).

Aqui está o nó da classe para a lista vinculada:

public class LinkedNode{
    public LinkedNode next;
}

Aqui está o código principal com um caso de teste simples de três nós que o último nó apontando para o segundo nó:

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

Aqui está um caso de teste simples de três nós que o último nó apontando para o segundo nó:

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

Esse código é otimizado e produzirá resultados mais rapidamente do que o escolhido como a melhor resposta. Esse código evita o processo muito longo de perseguir o ponteiro de nó para frente e para trás, que ocorrerá no caso a seguir, se seguirmos o 'melhor responda '. Observe o procedimento a seguir e você perceberá o que estou tentando dizer. Depois, observe o problema pelo método abaixo e meça o não. das medidas tomadas para encontrar a resposta.

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

Aqui está o código:

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
}

Aqui está a minha solução em 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;
}

Você também pode usar o algoritmo de tartaruga de Floyd, como sugerido nas respostas acima.

Esse algoritmo pode verificar se uma lista vinculada individualmente possui um ciclo fechado. Isso pode ser alcançado iterando uma lista com dois ponteiros que se moverão em velocidade diferente. Dessa forma, se houver um ciclo, os dois indicadores se encontrarão em algum momento no futuro.

Por favor, sinta-se livre para conferir meu blog no na estrutura de dados das listas vinculadas, onde também incluí um trecho de código com uma implementação do algoritmo mencionado acima na linguagem java.

Saudações,

Andreas (@xnorcode)

Aqui está a solução para detectar o ciclo.

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 
        }

// função de loop de localização de lista vinculada

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

Essa abordagem possui sobrecarga de espaço, mas uma implementação mais simples:

O loop pode ser identificado armazenando nós em um mapa. E antes de colocar o nó; verifique se o nó já existe. Se o nó já existir no mapa, significa que a Lista vinculada tem loop.

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

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;

}