Saturday, October 25, 2014

Detecting an Infinte Loop in a Linked List - Java

Question: If you have a linked list in which you can traverse only in one direction, and if that linked list has a loop in it, how you will detect it?

Algorithm (Floyd's cycle-finding algorithm):

1. Initialize two pointers p1 (to head) and p2 (to head.next.next). 
2. Both traverse the list but p2 is say 2 steps ahead of p1.
3. If the list has a cycle, p1 and p2 will be equal at some time.
4. If the list doesn't have a cycle, p2 will be pointing to null.

Source:

class Node { 
    int value;
    Node next;
}

public class InfiniteLoop {

    private static Node makeCyclicList() {  
        
        Node head = new Node(); 
        head.next = new Node();
        head.next.next = new Node();
        head.next.next.next = new Node();
        head.next.next.next.next = new Node();
        head.next.next.next = head.next;
        
        return head;
    }

    private static Node makeNonCyclicList(){ 
        
        Node head = new Node(); 
        head.next = new Node();
        head.next.next = new Node();
        head.next.next.next = new Node();
        head.next.next.next.next = new Node(); 
        
        return head;
    }

    public static boolean isInfinite(Node head){
        if(head==null) return false;
        
        Node p1 = head, p2 = head;
        
        if(p2.next==null)return false;
        p2 = p2.next.next;
        
        while(true){
            if(p1==p2) return true; 
            if(p2==null || p2.next == null) return false;
            p1 = p1.next;
            p2 = p2.next.next;
        } 
    }
    
    public static void main(String[] args) {
        System.out.println("List is "+(isInfinite(makeCyclicList())?"cyclic":"acyclic"));
        System.out.println("List is "+(isInfinite(makeNonCyclicList())?"cyclic":"acyclic"));
    }
}
Output:

List is cyclic
List is acyclic

No comments:

Post a Comment