Java를 사용하여 링크 된 목록에서 루프를 탐지하는 방법

목록의 모든 요소를 검사하고 표시된 요소를 저장하면 연결된 목록에서 루프를 감지 할 수 있습니다. 현재 요소가 이미 표시된 경우에는 루프가 있습니다.

사이클 탐지는 요소 추가 또는 집합에있는 요소의 테스트가 0 인 경우에 구현할 수 있습니다. 이전 노드의 사이클을 감지하면 이전 노드를 저장하여 사이클을 중단 할 수 있습니다 이전에 본 요소 대신 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

이 예제는 연결된 목록에서 루프가없는 호출과 연결된 목록에서 루프가있는 호출을 두 번 호출합니다.

참고 문헌 :

Linked List on wikipedia