How to detect loops in a Linked List in Java

03/11/2019

Loops can be detected in an Linked List by inspecting all the elements of the list and saving the element seen. If the current element has already been seen, then we have a loop.

The detection of cycles can be implemented using a Set as adding an element or testing if an element is in the set are in O of 1. The cycle can be broken by saving the previous node, once the cycle is detected the next Element from previous point to null instead of the element that has been previously seen. This implementation has the best performance as the algorithm is in O(n) where n is the number of elements in the list.

Create the following java file:

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

The output will be:

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

This example runs 2 calls one without a loop in the linked list and another one with a loop in the linked List.

References:

Linked List on wikipedia