Interview Bootcamp

0% completed

​

Solution: Start of LinkedList Cycle

Problem Statement

Given the head of a Singly LinkedList that contains a cycle, write a function to find the starting node of the cycle.

Solution

If we know the length of the LinkedList cycle, we can find the start of the cycle through the following steps:

  1. Take two pointers. Let’s call them pointer1 and pointer2.
  2. Initialize both pointers to point to the start of the LinkedList.
  3. We can find the length of the LinkedList cycle using the approach discussed in LinkedList Cycle. Let’s assume that the length of the cycle is ‘K’ nodes.
  4. Move ``pointer2`

.....

.....

.....

Like the course? Get enrolled and start learning!
L

lejafilip

· 2 years ago

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;
}
Show 1 reply