Linked List Questions: Detect a Cycle - Set or Hashtable Approach
Tags: algorithms, codenewbie, tutorial
Published: 2021-09-07 04:33:17

## Video Explanation
{% youtube 8zVzUl7v-ds %}

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
https://leetcode.com/problems/linked-list-cycle/

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
//if cycle was not found ie. 'if' condition was never met
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 of Linked List

```cpp
//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

```cpp
/* 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:
    bool hasCycle(ListNode *head)
    {

        unordered_set<ListNode *> nodes_seen;

        while (head != nullptr)
        {
            if (nodes_seen.count(head) > 0)
            {
                return true;
            }

            nodes_seen.insert(head);
            head = head->next;
        }
        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.