Como detectar loops em uma lista vinculada em Java

03/11/2019

Os loops podem ser detectados em uma lista vinculada, inspecionando todos os elementos da lista e salvando o elemento visto. Se o elemento atual já foi visto, então temos um loop.

A detecção de ciclos pode ser implementada usando um Set como adicionar um elemento ou testar se um elemento no conjunto está em O de 1. O ciclo pode ser quebrado salvando o nó anterior, uma vez que o ciclo é detectado o próximo Elemento do anterior aponte para null em vez do elemento que foi visto anteriormente. Essa implementação tem o melhor desempenho, pois o algoritmo está em O (n), onde n é o número de elementos na lista.

Crie o seguinte arquivo java:

import java.util.HashSet;
import java.util.Set;

public class InterviewLinkedListCycle {

    public static boolean testLoopON( Node head, boolean removeCycle ){
        // Input Validation
	if( head == null )
	    throw new IllegalArgumentException( "Input cannot be null" );
	
        //Processing.
        Set<Integer> seen = new HashSet<Integer>();
        
        // save the head
        Node current = head;
        
        // Save the previous node
        Node previous = null;
        
        // Loop on elements
        while( current != null ) {

            // Check for the cycle
            if ( seen.contains( current.data ) ){
                
        	if( removeCycle ){
        	    // Break the loop
        	    previous.next = null;
        	}
        	
                // We have found a loop
                return true;
            }
            
            seen.add( current.data );
            
            previous = current;
            current = current.next;
        }
        
        // No Loop found
        return false;
    }
    
    public static void main(String[] argv) throws Exception {
	InterviewLinkedListCycle t = new InterviewLinkedListCycle();
	
	Node head = new Node(1);
	Node current = head;
	for( int i = 2; i < 10 ; i++ ){
	    current.next = new Node(i);
	    
	    current = current.next;
	}

	long before = System.nanoTime();
	boolean found = testLoopON( head, true );
	long after = System.nanoTime();
	System.out.println( "Loop found = " + found + " in " + (int)(after-before)/1000 + " \u00B5 seconds"  );
	
	// Create the Loop
	current.next = head.next;

	before = System.nanoTime();
	found = testLoopON( head, true );
	after = System.nanoTime();
	System.out.println( "Loop found = " + found + " in " + (int)(after-before)/1000 + " \u00B5 seconds"  );

    }
    
}

class Node {
    Node(Integer data){
	this.data = data;
    }
    
    Integer data;
    Node next;
}

O resultado será:

Loop found = false in 34 \u00B5 seconds
Loop found = true in 15 \u00B5 seconds

Este exemplo executa duas chamadas, uma sem loop na lista vinculada e outra com um loop na Lista vinculada.

Referências:

Linked List on wikipedia