How to detect a cycle in linked list in C++

Problem

In this shot, we will discuss a commonly asked interview question on coding. In this problemWe will solve this problem using C++, although a similar idea applies to other programming languages., we are given a linked list and told to find whether or not it contains a cycle.

A linked list contains a cycle if one node is connected to another node that we have already traversed. To understand this better, let’s look at the snapshot below, which depicts a linked list containing a cycle.

Linked List containing a cycle

Solution

In the snapshot above, we can see that the last node points back to the third node instead of storing a NULL value.

We can use the hashing concept to solve this problem. The idea is to traverse each node in the linked list and, once we traverse it, insert the node to a set. We will need to check if the node that we are currently traversing is already present in the set. If it is already present, we can say that there is a cycle in the linked list.

Before we move on to coding, let’s look at the time complexity of this solution. We would be traversing N nodesworst case: cycle present at the last node that would take O(N). To check the node in the set, we use O(1) because sets are implemented through hashingin hashing, lookup is of constant time. So, overall, the complexity would be O(N).

Now, let’s take a look at the code.

Code

#include <iostream>
#include <unordered_set>
using namespace std;
bool containsCycle(Node *head){
unordered_set<Node*> nodes_traversed;
while(head != NULL){
if(nodes_traversed.count(head) != 0)
return true;
nodes_traversed.insert(head);
head = head->next;
}
return false;
}
int main() {
int keys[] = { 1, 2, 3, 4, 5 };
int n = sizeof(keys) / sizeof(keys[0]);
Node* head = nullptr;
for (int i = n - 1; i >= 0; i--)
push(head, keys[i]);
head->next->next->next->next->next = head->next->next;
if (containsCycle(head))
cout << "Cycle Found";
else
cout << "No Cycle Found";
}

Explanation

  • In lines 1 and 2, we import the required libraries.
  • In line 5, we create a containsCycle() function that accepts the head of the linked list and returns true. This indicates that there is a cycle presentreturns false if no cycle is found.
  • From lines 6 to 14, we implement the idea that was discussed above. We use the set to store the nodes, then check if we have already traversed the current node to check for the cycle.
  • In the main() function, we simply create a linked list and then add a cycle in the linked listThe linked list looks the same as the snapshot above..
  • Finally, in lines 24 to 27, we print whether the cycle is present or not.

Conclusion

This is a highly common interview question where the interviewer evaluates your ability to apply the correct data structure to solve the problem in the lowest time complexity possible.

Check out my course Competitive Programming - Crack Your Coding Interview, C++ for additional help on how to prepare for coding interviews.

Free Resources