Detect a Cycle in a Linked List (3 methods)| Coding Interview | Linked List | Hard

This is one of the popular problems from the linked list as it deals with cycles. I will discuss three approaches to solve the problem, each one better than the previous one. This problem was asked by companies like Amazon, Accolite, MAQ Software, and Samsung.

If you preparing for a coding interview, then you will definitely find this article helpful.

[embed]30 Days Interview Preparation Plan: 200+ best coding questions and Behavioural interviews I have collected these questions from several great sources like geeksforgeeks, leetcode, interview experiences …ganeshpr227.medium.com

Let’s begin with the table of contents we will cover.

Table of Contents

1. Description
2. Solution using** Hash Table**
3. Code
4. Solution using** one extra node**
5. Code
6. Solution** without any extra space**
7. Code

Description

We are given a linked list, and we have to tell whether it has a loop/cycle or not. The figure below shows an example of a linked list with and without a cycle.

Solution with Hash Table

It is clear to see that traversing a linked list with a loop will lead to traversing the nodes in the cycle again and again. Like, in the example above, If we start with node A, we will visit B, then C, D, and again C and D, and so on.

If we store the nodes that we visit in a hash table and use it to check if the current node has already been seen (present in the hash table). Then, we will know there is a cycle if we come across a node that is already present. If the linked list has no cycle, then we will reach the end of the list.

Algorithm to see if the linked list has a loop or cycle.

• Create a hash table to store references to the nodes of the linked list.
• Traverse the linked list node by node and check if the current node is present in the hash table.
• If the current node is not present in the hash table, then add the node to the table.
• If the node is present, then it means we are in a loop visiting the same nodes repeatedly.
• Hence, we are in a loop.

Let’s see this algorithm working on the example above. In the figure below, we have an empty hash table and a linked list with a loop.

The following is an example of what will happen if the linked list has no loop. The iterator will reach the nullptr, which will be a sign that we have reached the end, and thus list has no cycle.

Code (cpp)

Easy to understand code with comments.

[embed]

Time & Space Complexity

Time: Since we are iterating the list node by node with each node being traversed exactly once except the first node of the cycle, the approach is a linear one, O(n).

Space: We are using a hash table that stores all the nodes of the linked list; hence the space complexity is O(n).

Solution Using One Extra Node

In the previous approach, we used a hash table to remember the nodes that we have already traveled so that if we enter the cycle and see a node that is already seen, we will say there’s a cycle. There’s another way to remember which nodes have been traveled without using a data structure of length n.

We can create a single temporary node to remember nodes that we have already seen. How? by pointing the traveled nodes to this temporary node. Every time we visit a new node, we will set is next pointer to this node, and if we come across a node that is already pointing to the temporary node, then it means we are in a cycle.

Let’s see a working example. In the following example, we have a temporary node in black color and a linked list with a cycle.

We start traversing the linked list and check if the current node’s next pointer is equal to the temporary node; if not, then do so.

Node A is now pointing to the temporary node.

Node B is now pointing to the temporary node.

Node C is now pointing to the temporary node.

Node D is now pointing to the temporary node. When we moved to the next node of D, which is C, we checked if its next pointer was already pointing to the temp node. Since it is, we say that the linked list has a cycle.

Algorithm for finding the cycle in a linked list

1. Create a temporary node (temp).
2. Traverse the linked list, node by node.
3. For each node, check if it is pointing to the temp node.
4. If yes, then we are in a loop, meaning the list has a cycle.
5. If not, then set the node’s next pointer to the temp node.
6. If we reach the end of the list, it means that the list has no cycle.

Code (cpp)

Easy to understand code with comments.

[embed]

Time & Space Complexity

Time: Same as the previous approach, we traverse the linked list once. Hence, the time complexity is O(n), where n is the number of nodes in the list.

Space: We are not using any space proportional to the size of the linked list. Hence the space complexity is constant, O(1).

Solution without any extra space

For this approach, we will use the fast and slow pointer patterns. In the fast and slow pointer pattern, the fast pointer traverses a linked list at double the speed of the slow pointer. In other words, the slow pointer moves node by node, and the fast pointer moves by skipping a node.

If you start both the pointers from the first node, you will observe that after some traversing, the slow and fast pointers will again overlap. This will be clear with an example. But I will suggest that you try on linked lists of different sizes (It's fun to see that no matter what is the size of the loop, both pointers always overlap at some point in time).

You can see that the fast pointer moves from A to C instead of B, and the slow pointer moves to B.

When the fast pointer jumps over node D to point to C, the slow pointer also points to C. Overlap!!

Algorithm to find a cycle in linked list using fast and slow pointer

• Create 2 pointer variables, fast and slow.
• Traverse the linked list using these pointers starting from the head.
• Move the fast pointer to next to next node at a time.
• Move the slow pointer to the next node at a time.
• If, at any moment in time, the two overlap, then it means there is a cycle.

Code (cpp)

Easy to understand code with comments.

https://gist.github.com/PrasadGanesh/ed4556d181a9041bb4cf8c64d2c18f40

Time & Space Complexity

Time: Linear, as we are traversing the linked list once.

Space: Constant, as no extra space is used for this approach.

Thanks. If you like the article, read my other pattern-based problems.

If you liked what you just read, a clap 🤗🤗🤗would be highly appreciated. You can be generous in clapping; it shows me how much you enjoyed this story. And if you didn’t like it? Please do comment😋!

P.S.: If you like this uninterrupted reading experience on this beautiful platform of Medium.com, consider supporting the writers of this community by signing up for a membership HERE. It only costs $5 per month and helps all the writers.

You can also follow me HERE to get updates on my stories.

[embed]System Design 🔥 — Key Concepts and Terms [Interview Notes] This is a list of 20+ key terms and concepts in System Design, along with brief explanations for each.ganeshpr227.medium.com