3 different ways to detect a loop in a Linked List

How to detect a loop in a Linked list

In a linked list, last node of the list is obtained by searching for a null value in the address part of a node. However, if we do not find any node containing the null value, it indicates the presence of cycle/loop in the linked list. There are two possibilities for the presence of loop/cycle. Cycle may be from the last node or it can be from some intermediate node in the list as shown in the diagram.

There are three ways to detect a loop in a linked list. They are as listed below.

Advertisement
  • Traversing through the list
  • Using HashSet
  • Using Floyd's Cycle Detection Algorithm

 

Method-1: Traversing through the list

This is the traditional approach to detect a loop in a linked list. Here, we will traverse a list using two nested loops. Here, we are taking two pointers p and q. The pointer p will traverse from the first node to last node exactly once. However, the pointer q will every time start with first node and traverse till pointer p. Every time during looping q will check for whether it was pointing to the same node as p. If so, it means there is cycle.

// Program to detect a loop in a linked list
import java.util.HashSet;

// Node class
class Node {
    // class variables
    int data;
    Node next;

    // Constructor
    Node(int x) {
        data = x;
        next = null;
    }
}

// Main class
public class Main {
    public static void main(String args[]) {
        Node head = new Node(10);
        Node n1 = new Node(20);
        head.next = n1;
        Node n2 = new Node(30);
        n1.next = n2;
        Node n3 = new Node(40);
        n2.next = n3;
        Node n4 = new Node(50);
        n3.next = n4;

        // Creating loop
        n2.next = head;
        Main o = new Main();
        o.findcycle(head);
    }

    // Function to detect a loop
    public void findcycle(Node head) {
        // Initializing 
        Node p = head;
        int count = 0;

        // Traversing the Linked List.
        while (p != null) {
            // Initializing    
            Node q = head;

            p = p.next;
            count++;
            // Iterating q from first node till current node
            while (count > 0) {
                System.out.println("Comparing node " + p.data + " with " + q.data);
                if (q == p) {
                    System.out.println("Cycle found");
                    return;
                }
                q = q.next;
                count--;
            }
        }
    }
}

Output:

Comparing node 20 with 10
Comparing node 30 with 10
Comparing node 10 with 10
Cycle found

 

Method-2: Using HashSet

This is the simplest approach to detect a loop in a linked list. Firstly, we will create an empty hashset. Thereafter, we will traverse the nodes in the list one by one and store these node addresses in a hash table. Now, before inserting a node, we will check if the node is already present using the contains method of HashSet. If the current node is already present in the hash table, then it indicates that there is a loop in the linked list. However, if we reach to the end of the list and none of the nodes are repeated means that there is no loop in the linked list.

// Program to detect a loop in a linked list
import java.util.HashSet;

// Node class
class Node {
    int data;
    Node next;

    Node(int x) {
        data = x;
        next = null;
    }
}

// Main class
public class Main {
    public static void main(String args[]) {
        Node head = new Node(10);
        Node n1 = new Node(20);
        head.next = n1;
        Node n2 = new Node(30);
        n1.next = n2;
        Node n3 = new Node(40);
        n2.next = n3;
        Node n4 = new Node(50);
        n3.next = n4;

        // Creating loop
        n2.next = head;

        // Object creation and function calling
        Main o = new Main();
        o.findcycle(head);
    }

    // Function to detect a cycle    
    public void findcycle(Node head) {
        Node p = head;
        HashSet h = new HashSet < > ();

        // Traverse the Linked List.
        while (p != null) {
            System.out.println("Inserting node " + p.data);
            // Checking if current node is already present
            if (h.contains(p)) {
                System.out.println("Cycle found");
                return;
            }
            // Adding the current node as it was not previously added
            h.add(p);
            p = p.next;
        }
        System.out.println("Cycle not found");
    }
}

Output:

Inserting node 10
Inserting node 20
Inserting node 30
Inserting node 10
Cycle found

 

Method-3: Using Floyd’s Cycle Detection Algorithm

This is the fastest approach to detect a loop in a linked list. Here, we will maintain two pointer slow pointer(s) and fast pointer(f) that moves in the list one step and two step at a time respectively. If there is a loop in the linked list, both the pointers will meet at some node. However, if there is no loop then fast pointer will reach to the end of the list.

// Program to detect a loop in a linked list
import java.util.HashSet;

// Node class
class Node {
    // Class variables
    int data;
    Node next;

    // Constructor
    Node(int x) {
        data = x;
        next = null;
    }
}

// Main class
public class Main {
    public static void main(String args[]) {
        Node head = new Node(10);
        Node n1 = new Node(20);
        head.next = n1;
        Node n2 = new Node(30);
        n1.next = n2;
        Node n3 = new Node(40);
        n2.next = n3;
        Node n4 = new Node(50);
        n3.next = n4;

        // Creating loop
        n2.next = head;

        // Object creation and function calling
        Main o = new Main();
        o.findcycle(head);
    }

    // Function to detect cycle
    void findcycle(Node head) {
        Node s = head, f = head;
        int found = 0;
        while (s != null && f != null && f.next != null) {
            // s pointer moves 1 step everytime whereas f pointer moves two step at a time
            s = s.next;
            f = f.next.next;
            System.out.println("Slow pointer is at " + s.data);
            System.out.println("Fast pointer is at " + f.data);

            // if both the pointers point to the same node then there is a loop
            if (s == f) {
                found = 1;
                break;
            }
        }
        if (found == 1)
            System.out.println("Cycle found");
        else
            System.out.println("No cycle found");
    }
}

Output:

Advertisement
Slow pointer is at 20
Fast pointer is at 30
Slow pointer is at 30
Fast pointer is at 20
Slow pointer is at 10
Fast pointer is at 10
Cycle found

 

Summary

The knowledge of detecting loop in a linked list is very useful concept from the view point of data structure. In many situations, we will need to detect a loop in a linked list when multiple threads are inserting the data in the single list. So, we can use any of the approach discussed here. In this tutorial, we covered three different approaches to detect a loop in a linked list. As per the complexity and size of data in an application, we can choose an appropriate approach to detect a loop in a linked list.

We learned in detail about this with source code. All in all, this tutorial, covers everything that you need to know in order to have a clear view on detecting a loop in a Linked list.

 

References

HashSet Class

 

Didn't find what you were looking for? Perform a quick search across GoLinuxCloud

If my articles on GoLinuxCloud has helped you, kindly consider buying me a coffee as a token of appreciation.

Buy GoLinuxCloud a Coffee

For any other feedbacks or questions you can either use the comments section or contact me form.

Thank You for your support!!

Leave a Comment

X