Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement 
3.
Method 1: Using Nested Loops
3.1.
Algorithm
3.2.
Code
4.
Method 2: Using a Hashmap
4.1.
Algorithm
4.2.
Code
5.
Method 3: Floyd’s Cycle Detection
5.1.
Algorithm
5.2.
Code
6.
Frequently Asked Questions
6.1.
How do you detect a loop in a single linked list?
6.2.
How do you find the loop position in a linked list?
6.3.
What is the best way to detect a cycle in a linked list?
6.4.
How do you find the loop in a linked list in C++?
6.5.
What is a loop in a linked list?
6.6.
Is it possible to find a loop in a linked list?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Detect a Loop in a Linked List

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM
Linked List

Introduction

All of us are working hard to crack the interview in a dream company of ours. We are preparing for the interviews, practicing coding questions, and putting in our hundred percent. 

 

One important topic we should be well versed in is linked lists

I’m sure all of us have heard and even used linked lists.

Problems with linked lists are commonly given in coding interviews. One such question is to detect a loop in a linked list

 

In this article, we will learn the different methods to solve the problem. 

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. 

Linked List

 

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

Linked List

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. 

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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:

Linked List

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

Linked List Animation

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

//Method to detect loop in a linked list
/*  
    Time Complexity : O(N*N)
    Space Complexity : O(1)
    
    Where N is number of Nodes in Linked-List.
*/

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

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

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

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

 

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

/*  
    Time Complexity : O(N)
    Space Complexity : O(N)
    
    Where N is number of Nodes in Linked-List.
*/

#include <unordered_set>

bool detectCycle(Node *head)
{
    // Set to store the visited nodes.
    unordered_set<Node *> nodesSeen;
    
    while (head != NULL)
    {
        if (nodesSeen.count(head))
        {
            //  We reached some earlier node again thus we found a cycle.
            return true;
        }
        else
        {
            //  Add the node to hastset of already seen nodes.
            nodesSeen.insert(head);
        }
        head = head->next;
    }

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

 

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

/*  
    Time Complexity : O(N)
    Space Complexity : O(1)
    
    Where N is number of Nodes in Linked-List.
*/

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

    //  Slow Pointer - This will be incremented by 1 Nodes.
    Node *slow = head;
    //  Fast Pointer  - This will be incremented by 2 Nodes.
    Node *fast = head->next;
    
    while (slow != fast)
    {
        //  We reached the end of the List and haven't found any Cycle.
        if (fast == NULL || fast->next == NULL)
        {
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }

    //  We found a Cycle.
    return true;
}

 

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 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.   

How do you find the loop position in a linked list?

If we use a hashmap to detect a loop in a linked list, we will find the address which is repeated, i.e., we can use it to detect the start of the loop in the linked list. This is how we’ll find the loop position in a linked list.

What is the best way to detect a cycle in a linked list?

The best way to detect a loop in a linked list is by using Floyd's cycle.

How do you find the loop in a linked list in C++?

We can detect loops in a linked list using different algorithms, some of which are mentioned above in C++.

What is a loop in a linked list?

A loop in a linked list may be thought of as a circular linked list within a singly linked list, as shown below:

Linked List

 

Is it possible to find a loop in a linked list?

Yes, it is possible to detect a loop in a linked list.

Conclusion

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

 

After learning about a loop in a linked list, the next thing we 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 in Coding Ninjas Studio. Along with coding questions, we can also find the interview experience of scholars working in renowned product-based companies here. 

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy learning!

Previous article
Clone a Linked List with Next and Random Pointer
Next article
Length of the Loop in the Linked List
Live masterclass