Problem
Given a circular linked list, implement an algorithm which returns node at the beginning of the loop. If there is no cycle, return null.
Try solving it using constant additional space.
Definition - Circular Linked List
A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
This is extension of Linked List Cycle 1 - Detect Cycle
Example
Example 1
Input:
head = [0, 1, 3, 2, 4]
output:
2
Explanation: Cycle starts at node 2
Example 2
Input:
head = [1, 2, 3, 4, 5, 6]
output:
3
Explanation: Cycle starts at node 3
Solution
Method 1 - Using Hashmap
In first iteration, we add all the elements to hashmap of <Node, Boolean>. Initially boolean value is false. Now there are 2 cases:
- If we reach end of list, i.e. we get null, we return null as there is no cyle.
- If we see repeating, that means we completed first cycle. We start setting the boolean value for node to true, marking it as part of cycle.
- When we see the element in the list, and boolean value is true, that means we are entering second time, that means we are at the start of the cycle and we return this element.