This is a very common interview question. You are asked that 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??

Well, if you don’t know the answer then don’t be demoralize. My personal opinion is that these kind of questions does not evaluate the logical thinking of a candidate because problems like this have a very specific answer. Either you know it, or you don’t.

For this specific question, best answer interviewer is looking for is “`Floyd's Cycle-Finding Algorithm`“. This algorithm suggest a solution in which in stead of only one pointer to traverse through list, you are advised to have two pointers at a time. Both pointers will start from first node of linked list and traverse using next attribute.

The difference lies in the number of nodes which they jump in each step. First node jump to next node each time, where as another node jumps two nodes at a time. First node is called slower node or tortoise, and second faster node is called hare.

Tortoise and hare algorithm

This traversal ensures that if there is a loop in linked link then both the nodes will meet somewhere in their traversal path for sure. It has O(n) complexity.

Lets verify this using a java example code.

I have written a least possible single linked list code for demonstration of this example only.

```package com.howtodoinjava.demo.core;

private Node start;

{
Node node = new Node(i);
if(start == null)
start = node;
else
{
Node temp = start;
while(temp.next != null)
{
temp = temp.next;
}
temp.next = node;
}
}

public Node getStart()
{
return start;
}

static class Node
{
Node(Integer i)
{
this.value = i;
}

private Integer value;
private Node next;
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
}

```

Now, let test above linked list first without loop and then with loop inside it.

```package com.howtodoinjava.demo.core;

{
public static void main(String args[]) {

// First Insert randomly ten elements in a linked list
for (int i = 0; i < 10; i++) {
}

System.out.println("Loop Existence : " + finder.doesLoopExist(sampleList));
System.out.println("Loop Existence : " + finder.doesLoopExist(finder.createLoop(sampleList)));
}

try {
while (true) {
tortoise = tortoise.getNext();
hare = hare.getNext().getNext();
if (tortoise == hare) {
return true;
}
}
} catch (NullPointerException ne) {
return false;
}
}

sampleList.getStart().getNext().getNext().getNext().setNext(sampleList.getStart().getNext());
return sampleList;
}
}

```

In above program, we have creates a linked list and the we inserted 10 elements in this list. No, when we checked the loop presence in line no. 15 it comes as false.

But, when in line 167, we have created a loop inside linked list result comes as true.

Output of above program is this:

```Loop Existence : false            [Line 15]
Loop Existence : true             [Line 16]
```

As you see, as soon as we insert loop in line no. 16, our algorithm implemetation is able to detect it.

Happy Learning !!

The following two tabs change content below.

#### Lokesh Gupta

Senior Analyst at Bank of America

I love to discuss things and that’s exactly why I am here. In java, I have around 7 Yrs of experience which has only increased my hunger for learn. In this blog, i will be writing on different topics occasionally, and would really love to engage in some meaningful serious discussions with you folks. I hope to hear from all your lovely people.