Detect Loop in Linked List - Naukri Code 360

Introduction

Detecting loops in linked lists is a fundamental problem in computer science and forms a critical part of algorithmic thinking. Linked lists, a linear data structure, are characterized by their dynamic memory allocation and flexibility. However, their lack of random access makes detecting cycles or loops within them a challenging task. In this blog, we delve into various approaches and algorithms used to detect loops in linked lists.

Problem Statement

As the name suggests, our problem of cycle detection in linked lists involves looking for a loop in a linked list.

We know what a standard linked list looks like.

However, a singly linked list may also have a loop in it as follows:

Thus, a loop occurs when a node points back to any of the previous nodes in the list.

In this condition, the linked list is no longer linear and cycles through a loop of nodes.

In our question, we have to detect a loop in the linked list.

Now that we know what our question is, let us see the different methods to solve it.

Method 1: Using Nested Loops

This is the easiest method that will naturally come to our mind but is inefficient with respect to time complexity.

Here, we will use an outer loop that iterates through the linked list and an inner loop that iterates through the linked list for each element to check for a loop.

Let’s see an illustration to understand this better.

Consider the linked list:

We will detect a loop in a linked list as follows:

Algorithm

Step 1: Create a nested loop with outer and inner loops, respectively. Maintain a count of the number of nodes visited in the outer loop.

Step 2: Start the outer loop from the head node and traverse through the entire linked list. 

Step 3: Start the inner loop from the node after the outer loop node and traverse. 

Step 4: If the outer and inner loop nodes are the same, return true.

Step 5: If not, continue iterating through the entire linked list.

Step 6: If the inner loop node is NULL at the end of all the iterations, return false.

Code

C++
Java
Python

C++

#include <iostream>

struct Node {
    int val;
    Node* next;
    Node(int val) : val(val), next(nullptr) {}
};

bool detectCycle(Node* head) {
    int numberOfNodesPassed = 0;
    Node* outerLoopNode = head;

    // Iterating over the linked-list.
    while (outerLoopNode != nullptr) {
        numberOfNodesPassed++;
        outerLoopNode = outerLoopNode->next;
        Node* innerLoopNode = head;
        int counterForInnerLoop = numberOfNodesPassed;

        // Iterating again from the beginning.
        while (counterForInnerLoop--) {
            // We found a repetitive Node/ Cycle.
            if (innerLoopNode == outerLoopNode) {
                return true;
            }
            innerLoopNode = innerLoopNode->next;
        }
    }

    // We didn't find any Cycle.
    return false;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);

    // Creating a loop for testing (4 -> 2)
    head->next->next->next->next = head->next;

    bool hasCycle = detectCycle(head);
    std::cout << "Linked List has cycle: " << (hasCycle ? "true" : "false") << std::endl; // Output: true

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

class ListNode {
    int val;
    ListNode next;
    
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedListCycleDetector {
    public boolean detectCycle(ListNode head) {
        int numberOfNodesPassed = 0;
        ListNode outerLoopNode = head;

        // Iterating over the linked-list.
        while (outerLoopNode != null) {
            numberOfNodesPassed++;
            outerLoopNode = outerLoopNode.next;
            ListNode innerLoopNode = head;
            int counterForInnerLoop = numberOfNodesPassed;

            // Iterating again from the beginning.
            while (counterForInnerLoop-- > 0) {
                // We found a repetitive Node/ Cycle.
                if (innerLoopNode == outerLoopNode) {
                    return true;
                }
                innerLoopNode = innerLoopNode.next;
            }
        }

        // We didn't find any Cycle.
        return false;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);

        // Creating a loop for testing (4 -> 2)
        head.next.next.next.next = head.next;

        LinkedListCycleDetector detector = new LinkedListCycleDetector();
        boolean hasCycle = detector.detectCycle(head);
        System.out.println("Linked List has cycle: " + hasCycle); // Output: true
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

def detectCycle(head):
    numberOfNodesPassed = 0
    outerLoopNode = head

    # Iterating over the linked-list.
    while outerLoopNode is not None:
        numberOfNodesPassed += 1
        outerLoopNode = outerLoopNode.next
        innerLoopNode = head
        counterForInnerLoop = numberOfNodesPassed

        # Iterating again from the beginning.
        while counterForInnerLoop > 0:
            # We found a repetitive Node/ Cycle.
            if innerLoopNode == outerLoopNode:
                return True
            innerLoopNode = innerLoopNode.next
            counterForInnerLoop -= 1

    # We didn't find any Cycle.
    return False

# Example usage:
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)

# Creating a loop for testing (4 -> 2)
head.next.next.next.next = head.next

hasCycle = detectCycle(head)
print(f"Linked List has cycle: {hasCycle}")  # Output: True

You can also try this code with Online Python Compiler

Run Code

Method 2: Using a Hashmap

This method is a simple one to detect a loop in a linked list.

Here, A linked list is traversed and as we visit each node, its address is stored in a hash table. We know a hash table cannot have duplicate keys, so it checks if we are revisiting the node. This helps detect loops in a linked list.

Algorithm

Step 1: Initialize a temporary variable (temp) with 0.

Step 2: Create a hashmap

Step 3: Traverse through the linked list

Step 4: Check if the address of the current node is present in the hashmap

Step 5: If it is, print that the loop is found and assign 1 to temp 

Step 6: Else, insert the address in the hashmap

Step 7: After traversing, if temp is equal to 0, print that no loop has been found

Code

C++
Java
Python

C++

#include <iostream>
#include <unordered_set>

struct Node {
    int val;
    Node* next;
    Node(int val) : val(val), next(nullptr) {}
};

bool detectCycle(Node* head) {
    std::unordered_set<Node*> nodesSeen;

    while (head != nullptr) {
        if (nodesSeen.count(head)) {
            // We reached some earlier node again, thus we found a cycle.
            return true;
        } else {
            // Add the node to the hash set of already seen nodes.
            nodesSeen.insert(head);
        }
        head = head->next;
    }

    // We didn't find any Cycle.
    return false;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);

    // Creating a loop for testing (4 -> 2)
    head->next->next->next->next = head->next;

    bool hasCycle = detectCycle(head);
    std::cout << "Linked List has cycle: " << (hasCycle ? "true" : "false") << std::endl; // Output: true

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.HashSet;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedListCycleDetector {
    public boolean detectCycle(ListNode head) {
        HashSet<ListNode> nodesSeen = new HashSet<>();

        while (head != null) {
            if (nodesSeen.contains(head)) {
                // We reached some earlier node again, thus we found a cycle.
                return true;
            } else {
                // Add the node to the hash set of already seen nodes.
                nodesSeen.add(head);
            }
            head = head.next;
        }

        // We didn't find any Cycle.
        return false;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);

        // Creating a loop for testing (4 -> 2)
        head.next.next.next.next = head.next;

        LinkedListCycleDetector detector = new LinkedListCycleDetector();
        boolean hasCycle = detector.detectCycle(head);
        System.out.println("Linked List has cycle: " + hasCycle); // Output: true
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

def detectCycle(head):
    nodes_seen = set()

    while head is not None:
        if head in nodes_seen:
            # We reached some earlier node again, thus we found a cycle.
            return True
        else:
            # Add the node to the set of already seen nodes.
            nodes_seen.add(head)
        head = head.next

    # We didn't find any Cycle.
    return False

# Example usage:
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)

# Creating a loop for testing (4 -> 2)
head.next.next.next.next = head.next

hasCycle = detectCycle(head)
print(f"Linked List has cycle: {hasCycle}")  # Output: True

You can also try this code with Online Python Compiler

Run Code

Method 3: Floyd’s Cycle Detection

Floyd’s cycle detection algorithm is used to check whether the linked list contains a cycle or not. It uses a two runner approach to do so. Let’s first understand this algorithm in brief.

Algorithm

Step 1: The idea is to have 2 pointers: slow and fast. Slow pointer takes a single jump and corresponding to every jump slow pointer takes, fast pointer takes 2 jumps. If there exists a cycle, both slow and fast pointers will reach the exact same node. If there is no cycle in the given linked list, then the fast pointer will reach the end of the linked list well before the slow pointer reaches the end or null.

Step 2: Initialize slow and fast at the beginning.

Step 3: Start moving slow to every next node and moving fast 2 jumps, while making sure that fast and its next is not null.
Step 4: If after adjusting slow and fast, if they are referring to the same node, there is a cycle otherwise repeat the process
Step 5: If fast reaches the end or null then the execution stops and we can conclude that no cycle exists.

Code

C++
Java
Python

C++

#include <iostream>

struct Node {
    int val;
    Node* next;
    Node(int val) : val(val), next(nullptr) {}
};

bool detectCycle(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return false;
    }

    Node* slow = head;
    Node* fast = head->next;

    while (slow != fast) {
        if (fast == nullptr || fast->next == nullptr) {
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }

    return true;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);

    // Creating a loop for testing (4 -> 2)
    head->next->next->next->next = head->next;

    bool hasCycle = detectCycle(head);
    std::cout << "Linked List has cycle: " << (hasCycle ? "true" : "false") << std::endl; // Output: true

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

class ListNode {
    int val;
    ListNode next;
    
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedListCycleDetector {
    public boolean detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode slow = head;
        ListNode fast = head.next;

        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }

        return true;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);

        // Creating a loop for testing (4 -> 2)
        head.next.next.next.next = head.next;

        LinkedListCycleDetector detector = new LinkedListCycleDetector();
        boolean hasCycle = detector.detectCycle(head);
        System.out.println("Linked List has cycle: " + hasCycle); // Output: true
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

def detectCycle(head):
    if head is None or head.next is None:
        return False

    slow = head
    fast = head.next

    while slow != fast:
        if fast is None or fast.next is None:
            return False
        slow = slow.next
        fast = fast.next.next

    return True

# Example usage:
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)

# Creating a loop for testing (4 -> 2)
head.next.next.next.next = head.next

hasCycle = detectCycle(head)
print(f"Linked List has cycle: {hasCycle}")  # Output: True

You can also try this code with Online Python Compiler

Run Code

This is the best method to detect a loop in a linked list in terms of

Time complexity- O(N)

Space complexity- O(1).

Watch this video to know how to detect the loop in the linked list with the proper concept.

Now that we have a basic understanding of how to detect loop in a linked list, let’s submit it on Coding Ninjas Studio and get it accepted right away.

We will also be able to solve related problems like, finding the first node of the loop and removing the loop. We can try solving those problems in the following links:

Frequently Asked Questions

How do you find a cyclic linked list?

An efficient algorithm uses two pointers, slow and fast. Slow moves one step at a time, and fast moves two steps at a time. If there's a cycle, the fast pointer will eventually lap the slow pointer, indicating a loop.

What is the cycle detection problem?

The cycle detection problem asks if a linked list contains a loop. This loop occurs when a node's next pointer points back to a previously visited node, creating an infinite loop while traversing the list.

Can BFS be used to detect cycles?

Breadth-First Search (BFS) explores nodes level by level. It's not ideal for cycle detection in linked lists as BFS focuses on reaching all nodes, not revisiting them. The two-pointer method specifically checks for revisiting nodes.

How do you detect a loop in a single linked list?

We can detect loops in a linked list using different algorithms, some of which are mentioned above. The best solution is by using Floyd's cycle.

Conclusion

In this article, we learned about the problem in which we have to detect loop in linked list. We learned about the different algorithms to solve the problem, but that’s not enough.

After learning about a loop in a linked list, the next thing you need to learn is how to find the length of a loop in a linked list.

Apart from this, you can find a wide range of coding questions commonly asked in interviews at Naukri Code 360. Along with coding questions, we can also find the interview experience of scholars working in renowned product-based companies here.

Happy learning!