如何在Java中檢測鍊錶中的循環

03/11/2019

通過檢查列表的所有元素並保存所看到的元素，可以在鏈接列表中檢測循環。 如果已經看到當前元素，那麼我們有一個循環。

可以使用Set作為添加元素或測試集合中的元素是否為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

最近評論