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

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

//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:
    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.