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: Implementation using Java: class DetectLoop{
Node head;

//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
new_node.next = head;

//head points to new node
head = new_node;
}

void loopDetection()
{
Node slow = head, fast = head;
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.head.next.next.next.next = list.head;

list.loopDetection();
}
} Output:
Loop Detected *In the following blogs we will discuss remaining methods Happy Coding! Follow us on Instagram @programmersdoor Join us on Telegram @programmersdoor Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem. Follow Programmers Door for more. #blog #interview #placement #learn #computer #science

        Contact Us

programmersdoor@gmail.com

  • LinkedIn
  • Facebook
  • Instagram

©2023 by Programmers Door