Harman Kadron Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Hi Ashish,
first of all, Nice code. But i didn't understand the below code snippet logic.
//there is a loop and the below snippet finds the node pointed back
while(fast != head){
fast = fast->next;
head = head->next;
}
Is it true that "fast" and "head" points move the same distance before reaching the intersection node.
My understanding is that "head' point needs to move it's pointer for each cycle (fast) and check whether head and fast pointers are equal.
Can you explain this code snippet logic ?
Yes, it will always be true that "fast" and "head" points move the same distance before reaching the intersection node. You can do a dry run by taking an example which will clear your doubt.
Also I did a mistake in the above code which I have rectified :
this
head = fast = slow;
should be
head = fast = slow = LL;
Hi Ashish,
I'm confused with below:
if(!fast->next && !fast->next->next) -- why inverted values?
It'd be good if you can briefly comment how this overall code is working:
I think moving one pointer twice at speed of other is self evident, its like two people jogging on a circular track. the faster one will eventually meet the slower one.
Finding the node where the loop begins is interesting.
Lets say fast and slow meet at point p
head-------loopbegin------------meetingPoint----------pointingtoLoopBegin
Lets say head->LoopBegin = x
loopBegin->meetingPoint = y
meetingPoint -> pointingToLoopbegin = z
distance travelled by slow node = x +y
distance travelled by faster one = x + y + z + y
so as t = d/s and t(slower) = t(faster)
(x+y)/s = (x+2y+z)/2s
solving it will give x = z;
I think we could simply maintain a list of visitedNodes. So during iteration if we find any node thats already part of visited node list then we could say we have loop provided the list does not any duplicates.
If duplicates we need to come up with hashcode for each node and do comparison. Hope that make sense. Anyways following is the java snippet that should tell you loops and the link thats actually causing the loop (for no duplicates scenario)
List visitedNodes = new ArrayList();
ListNode prevNode = null;
tempNode = headNode;
while(!visitedNodes.contains(tempNode) && tempNode.nextNode != null){
visitedNodes.add(tempNode);
prevNode = tempNode;
tempNode = tempNode.nextNode;
}
if(tempNode.nextNode != null){
System.out.println("Link from "+ prevNode.toString()+ " to " + tempNode.toString() +" causing cycles");
}
Please refer to ostermiller.org/find_loop_singly_linked_list.html.
You don't have to use a "visited flag" or additional information, just a slow iterator and a fast iterator. The " The Tortoise and the Hare Algorithm".
// Best solution
function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
if (slowNode == fastNode1 || slowNode == fastNode2) return true;
slowNode = slowNode.next();
}
return false;
}
You can find out the cycle or loop in a single linked list by using two pointer approach.
Below link can be useful to find out the algorithm to find cycle or loop in linked list
<a href="newtechnobuzzz.blogspot.in/2014/07/how-to-find-loops-or-cycles-in-linked.html">newtechnobuzzz.blogspot.in/2014/07/how-to-find-loops-or-cycles-in-linked.html</a>
- Ashish June 03, 2013