Citigroup Interview Question
Country: India
Interview Type: In-Person
The problem is somewhat similar to finding the duplicate in a list of values. What we can do is maintain a hashSet of nodes. We will traverse the nodes one by one and will insert their references in the HashSet. If the node is already present in the hashSet we find a cycle on that node. The complexity will be O(n) for traversing the linkedList and O(1) for insertion. The pseudo code for the same will be something like:
1. Initialize HashSet<Node> hashSet = new HashSet<Node>();
2. Initialize the root to the firstElement of the list
3. while null != root do steps (a) and (b)
a) boolean addedSuccessfully = hashSet.add(root)
b) if NOT addedSuccessfully
return the root; cycle exists at root
else root = root.next ; continue with loop
node * find_start(node * n)
{
node * slow = n;
node * fast = n;
do
{
slow = slow->next;
fast = (fast->next)->next;
}
while((slow != fast)&&(fast!=NULL))
if(fast == NULL)
{
printf("No loop found");
return NULL;
}
else
return slow;
}
The idea is to have 2 pointers , with one going at double the speed, at some point the 2 pointers will point to the same node.
If length of loop is even, it'll finish in one iteration, else 2. Either case O(n)
There are a few good methods to find the starting point of the loop.
I will discuss 2 of them:-
Method 1:-
Method 2:- Efficient way
- pulkit.mehra.001 April 07, 2014