# Problem
In this shot, we will discuss a commonly asked interview question on coding. In this #key# problem: We will solve this problem using C++, although a similar idea applies to other programming languages. #key#, 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.

# 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 #key# N nodes: worst case: cycle present at the last node #key#  that would take *O(N)*. To check the node in the set, we use *O(1)* because sets are implemented through #key# hashing: in hashing, lookup is of constant time #key#. So, overall, the complexity would be *O(N)*.

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";
  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 #key# present: returns `false` if no cycle is found #key#.
* 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 #key# linked list: The linked list looks the same as the snapshot above. #key#. 
* 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++](https://www.educative.io/courses/competitive-programming-intvw?aff=xg3L) for additional help on how to prepare for coding interviews.

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

Traverse the linked list, storing nodes in a set. If a node repeats, a cycle exists.

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

Problem

Solution

Code

Explanation

Conclusion