## How to detect loops in a Linked List in Java

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 static boolean testLoopON( Node head, boolean removeCycle ){
// Input Validation
throw new IllegalArgumentException( "Input cannot be null" );

//Processing.
Set<Integer> seen = new HashSet<Integer>();

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

previous = current;
current = current.next;
}

// No Loop found
return false;
}

public static void main(String[] argv) throws Exception {

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

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.