Cómo detectar bucles en una lista enlazada usando Java

03/11/2019

Los bucles pueden detectarse en una lista vinculada inspeccionando todos los elementos de la lista y guardando el elemento visto. Si el elemento actual ya ha sido visto, entonces tenemos un bucle.

La detección de ciclos se puede implementar usando un Conjunto como adición de un elemento o prueba si un elemento está en el conjunto. Están en O de 1. El ciclo se puede romper al guardar el nodo anterior, una vez que se detecte el siguiente Elemento anterior. apunta a nulo en lugar del elemento que se ha visto anteriormente. Esta implementación tiene el mejor rendimiento ya que el algoritmo está en O (n) donde n es el número de elementos en la lista.

Crea el siguiente archivo 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;
}

El resultado será:

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

Este ejemplo ejecuta 2 llamadas una sin un bucle en la lista enlazada y otra con un bucle en la lista enlazada.

Referencias

Linked List on wikipedia