Javaを使用してリンクリスト内のループを検出する方法

リンクリストでループを検出するには、リストのすべての要素を調べて表示されている要素を保存します。 現在の要素がすでに表示されている場合は、ループがあります。

サイクルの検出は、セットを使用して要素を追加したり、セット内の要素が1のOにあるかどうかをテストしたりすることで実装できます。サイクルが検出されると、前のノードを保存する 以前に見られた要素の代わりにnullを指す。 この実装は、アルゴリズムがO(n)に含まれるため、最高のパフォーマンスを発揮します。nはリスト内の要素数です。

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

出力は次のようになります。

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

この例では、リンクリストにループのない呼び出しとリンクリストにループがある呼び出しの2つの呼び出しを実行します。

参考文献:

Linked List on wikipedia