Search

# Detect loop in Linked List

In this blog, we will learn to check if the list has a loop or not. The below diagram shows a linked list with a loop.

There are three different methods which can be used to detect a loop which are:

• Hashing

• Mark visited Nodes

• Floyd's Cycle-Finding Algorithm

But in this blog, we will discuss only Floyd's Cycle-finding Algorithm because it is the best approach with the Time complexity of O(n) and Space Complexity of O(1).

### Floyd's Cycle-Finding Algorithm:

• This is the fastest approach

• It uses two pointers for traversing

• Move one pointer (slow) by one and another pointer (fast) by two steps

• If these pointers meet at the same node then there is a loop and if not linked list doesn't have a loop

Below image depicts the loop_Detection function:

Loop_detection

### Implementation using Java:

```class DetectLoop{

//creates node
class Node{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}

//inserts a new node at front of the list
public void push(int new_data)
{
//put the data in new node
Node new_bode = new Node(new_data);

//makes next of new node as head

}

void loopDetection()
{
int flag = 0;
while(slow != null && fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
if(slow == fast)
{
flag = 1;
break;
}
}
if(flag == 1)
System.out.println("Loop Detected");
else
System.out.println("Loop not detected");
}

public static void main(String args[])
{
DetectLoop list = new DetectLoop();

list.push(20);
list.push(4);
list.push(15);
list.push(10);

//create a loop for testing

list.loopDetection();
}
}```
```Output:
Loop Detected```

*In the following blogs we will discuss remaining methods

Happy Coding!

Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.

See All