In this shot, we will discuss a commonly asked interview question on coding. In this
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.
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
Now, let’s take a look at the 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";elsecout << "No Cycle Found";}
containsCycle()
function that accepts the head of the linked list and returns true
. This indicates that there is a cycle false
if no cycle is foundmain()
function, we simply create a linked list and then add a cycle in the 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.