## Sunday, 22 May 2016

### Program to detect loop in a linked list in Java

Use Hashing:
Traverse the list one by one and keep putting the node addresses in a Hash Map. If next of current node points to any of the previously stored nodes in HashMap then return true.

Mark Visited Nodes:
This solution requires modifications to basic linked list data structure.  Have a visited flag with each node.  Traverse the linked list and keep marking visited nodes.  If you see a visited node again then there is a loop.

Floyd’s Cycle-Finding Algorithm - fastest method:
Traverse linked list using two pointers.  Move one pointer by one and other pointer by two.  If these pointers meet at some node then there is a loop.  If pointers do not meet then linked list doesn’t have loop.

Java code for Floyd’s Cycle-Finding Algorithm:

Node start;

/* Node - data & pointer for next node. */
class Node {
int data;
Node next;
Node(int d) {
data = d; next = null;
}
}

/* Inserts a new Node at start of list. */
public void push(int value) {

Node nNode = new Node(value);

/** Make next of new Node as start */
nNode.next = start;

/** Move the start to point to new Node */
start = nNode;
}

int detectLoop() {
Node pSlow = start;
Node pFast = start;
while (pSlow != null && pFast != null && pFast.next != null) {
pSlow = pSlow.next;
pFast = pFast.next.next;
if (pSlow == pFast) {
System.out.println("Found loop in list");
return 1;
}
}
return 0;
}
}

public class DetectLoopTest {

public static void main(String args[])  {

list.push(10);
list.push(40);
list.push(12);
list.push(13);

/** Create loop to test. */
list.start.next.next.next.next = list.start;

list.detectLoop();
}
}