Kathan Vakharia

Posted on

# Linked List Questions: Detect a Cycle - Set or Hashtable Approach

## Video Explanation

Note: In the youtube video above, I have explained 2 approaches. In this post, I'll explain the first one i.e. first 8 mins of the video.

If you are more into reading, continue with the blog. I would still suggest you at least download the annotations that I did in the video :)

## The Question

Given `head`, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next` pointer.

Return `true` if there is a cycle in the linked list. Otherwise, return `false`.

💡 Give yourself at least 15-20 mins to figure out the solution :)

## Explanation

The idea here is to traverse the list, and while doing that store the nodes in a `set`. If there's a cycle present, we'll try to insert a node(the starting point of cycle) for the second time, and as a `set` cannot have duplicate values, we can happily stop the algorithm by saying, YES there's a cycle in list. On the contrary, if a cycle is not present, we'll reach the end of the list and stop the algorithm by saying NO there's no cycle in the list.

Here's the pseudo code,

``````ListNode Node = head
Set s
while(Node != NULL)
if(s.contains(Node)) // a node is encountered second time
return true
else
s.insert(Node)
Node = Node.next
return false

``````

🗒 We are creating a set of node's addresses here NOT the node's values, Why? because node's addresses are unique in the list and values are not. For Example, 1→2→3→3→NULL doesn't contain a cycle but if we go by storing values in the set, the algorithm will say it does contain a cycle.

### Why `set`? (IMPORTANT)

Problem-solving is not just about solving questions, it is also about deciding proper data structure. Some of you may have this question, why did we use set here and not any other data structure?

Our need here is to perform two operations: store and lookup(read) from our data structure in every iteration and as a `set` is implemented as `hashtable` in programming languages, we can do O(1) insertion as well as lookup. So although you can use any data structure of your choice, `set` a.k.a `hashtable` is the best choice!

If you still have any doubts, you can refer the video explanation :)

## C++ Code

``````//Definition for singly-linked list.
struct ListNode
{
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};

``````

### Solution

``````/* A note about 'count(Key)'
*Searches the container for elements whose value is k and returns
*  the number of elements found
*Because unordered_set containers do not allow for duplicate keys,
*   this means that the function returns 1 if an element with
*   that value exists in the container, and zero otherwise.
*/
class Solution
{
public:
{

unordered_set<ListNode *> nodes_seen;

{
{
return true;
}

}
return false;
}
};
``````

## Complexity Analysis

`N`: Length of Linked List

### Time Complexity: O(N)

We are traversing the entire list and at every iteration, constant-time operations are done. ( and one more time if a cycle exists but asymptotically, it's still O(N) )

### Space Complexity: O(N)

We are storing every node exactly once.