**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