목록의 모든 요소를 검사하고 표시된 요소를 저장하면 연결된 목록에서 루프를 감지 할 수 있습니다. 현재 요소가 이미 표시된 경우에는 루프가 있습니다.
사이클 탐지는 요소 추가 또는 집합에있는 요소의 테스트가 0 인 경우에 구현할 수 있습니다. 이전 노드의 사이클을 감지하면 이전 노드를 저장하여 사이클을 중단 할 수 있습니다 이전에 본 요소 대신 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
이 예제는 연결된 목록에서 루프가없는 호출과 연결된 목록에서 루프가있는 호출을 두 번 호출합니다.