Interview Bootcamp
Ask Author
Back to course home

0% completed

Vote For New Content
5 lines solution for c++ by using hashSet. O(n) complexity.

lejafilip

Jul 19, 2024

Why we need to use slow/fast pointer approach while we can just store some unique value of each node? In c++ we can use memory address.

It is simply O(n), because we iterate over all list but we have also O(n) memory for HashSet.

Algorithm is simple. We need to iterate and add each pointer to hashSet until we come across already added one. Then return pointed address.

Code:

ListNode *findCycleStart(ListNode *head) { std::unordered_set<ListNode*> visitedNodes; ListNode* it = head; do { visitedNodes.insert(it); it = it->next; }while(!visitedNodes.contains(it)); return it; }

1

0

Comments
Shubham Vora
Shubham Vora2 years ago

In the interview, you need to solve the problem in the given time and space complexity. That's why space complexity is important.