## 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):

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() {

}

private static Node makeNonCyclicList(){

}

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