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.

Linked list with 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{
    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