リンクリストでループを検出するには、リストのすべての要素を調べて表示されている要素を保存します。 現在の要素がすでに表示されている場合は、ループがあります。
サイクルの検出は、セットを使用して要素を追加したり、セット内の要素が1のOにあるかどうかをテストしたりすることで実装できます。サイクルが検出されると、前のノードを保存する 以前に見られた要素の代わりにnullを指す。 この実装は、アルゴリズムがO（n）に含まれるため、最高のパフォーマンスを発揮します。nはリスト内の要素数です。
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;
}
Loop found = false in 34 \u00B5 seconds Loop found = true in 15 \u00B5 seconds
この例では、リンクリストにループのない呼び出しとリンクリストにループがある呼び出しの2つの呼び出しを実行します。