Grokking the Coding Interview: Patterns for Coding Questions
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
Comments
Shubham Vora
Shubham Voraa year ago

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