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

class LinkedList1 {

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[]) {

LinkedList1 list = new LinkedList1();

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

}

}

## No comments:

## Post a Comment