Microsoft Interview Question
Country: -
First half sounds pretty good. But once you know the length of the lists their difference is twice the number of nodes that are not in the loop - thus the index can easily be computed. Or I just don't get the "increment both by one till they meet" part.
"increment both by one until they meet" works.
Slow pointer went this far:
X (distance between beginning of list and start of circle) + Y (distance between beginning of list and meeting point).
Fast pointer went this far:
X (distance between beginning of list and start of circle)
+ Y (distance between beginning of list and meeting point) + Z (distance between meeting point and start of circle) +
Y (distance between beginning of list and meeting point)
We also know that the fast one went twice as fast as the slow one.
So 2 * (X + Y) = X + Y + Z + Y
Simplified X = Z
That is why it works.
Math win :-)
Ninja, you are correct, i missed the maths in it, with your explanation this is a much simpler problem.
The math is not correct. You're assuming that the fast pointer catches the slow pointer on the second iteration of the loop. But for lists with a large start section (without loops) and a small loop, the fast pointer will iterate the loop several time before the catching the slow pointer.
I still think that once you know both lists lengths you can calculate much easier the index. Once you detect the loop you can tell its length. And the overall list length can be determined if you reverse the links so you get back to the head. The difference in lengths/2 is the idx.
Right.
To summarize your solution:
1. find a node in the loop (one slow and one fast pointer solution) - O(n)
2. determine the length of the cycle (count the number of steps to reach again the loop node from itself) - O(n)
3. starting from the begining of the list reverse the links and count the nodes until the end - the nodes from the loop will be counted once and the ones from outside will be counted twice - O(n)
4. the index of the loop start element is (count step 3. - count step 2.)/2 - O(1)
1) Detect Loop using Floyd’s Cycle detection algo and get the pointer to a loop node.
2) Count the number of nodes in loop. Let the count be k.
3) Fix one pointer to the head and another to kth node from head.
4) Move both pointers at the same pace, they will meet at loop starting node.
1. you need to find the minimum and maximum number in that list
2. then increase every number by (maximum - minimum) iteratively, then the first number where you find it greater then maximum would be the first node of cycle in the list.
for finding the maximum and minimum number you can do through this way
take two iterater it1, it2
iterate it1 by one node
iterate it2 by two nodes
when these two iteraters meet for the 2nd time then it1 has visited all the nodes of linklist,
I think this will work
Numerical overflow. For example this algorithm will definitely not work if the list will contain the maximum representable number.
How about this one?
loop(List)
{
p1 and p2 are two pointers;
Initially p1 points to start of the list;
for(no of elements in list)
{
p2=p1;
while(p2!= null and p2!=p1)
p2=p2.next;
if(p2==p1) break; //node where loop starts
p1=p1.next;
}
}
Here for each node i will traverse the whole list with another pointer starting from that node and check whether that i reach that node again or not. If i reach the same node than that would be my start node.
Okay i thought he had told you no of elements.. Anyways its not even required to find the no of elements. Since it is given that there is only one loop here.
i can write the same as,
loop(List)
{
p1 and p2 are two pointers;
Initially p1 points to start of the list;
while(true)
{
p2=p1;
while(p2!= null and p2!=p1)
p2=p2.next;
if(p2==p1) break; //node where loop starts and hence i break from loop since there is only one loop here
p1=p1.next;
}
}
Yeah you correct. This is how i corrected my mistake. Tell me if this can work.
loop(List)
{
p1 and p2 are two pointers;
Initially p1 points to start of the list;
p2=p1.next;
int c=1;
while(check(p1,p2,c) and p2!=p1)
{ p2=p2.next;c++; }
/* p2!=p1 will see if loop starts at very 1st node and check function will check loop that starts at other than 1st node */
// p2 points to node where loop starts
}
check(p3,p4,c)
{
int d=1;
while(p3.next!=p4)
{ p3=p3.next;d++; }
if(c==d) return true;
else
if(d<c) return false;
/* when d id less than c, that means now for travelling from p3 to p4 took lesser traversals than for p2 traversing. That will happen incase of a loop. */
}
}
It seems to work, but it has O(n2)complexity
You should check "aaa"'s solution with O(n) complexity.
I used a recursive function to iterate the list. While iterating, I make the next pointer to NULL. The function will reach the node whose "next" is NULL. This is the node where loop starts. As my recursive function pulls back, it carries the loop-starting node backwards. Finally, matching the object with loop-starting node, my function figures out the its position in the list.
Node * FindPosition(Node * n, int position)
{
if(n->next == NULL)
return n;
Node * next = n->next;
n->next = NULL;
Node * ret = (FindPosition(next, position + 1);
if ( ret != NULL && ret == n)
cout<<"Position: "<<position<<endl;
n->next = next;
}
Lets start with two pointers approach.
- buch. October 03, 2011One gets incremented by one.
Other gets incremented by two.
And if there is a loop, pointers will meet at certain node. Lets call it "meeting point"
At this point, we have two linked list,
First our original link list (in the qustion), starting from start node.
Other one starting from the node next to our meeting point.
And now, this question transforms into "two link list joining at some node, find joining node at which they join".
Answer to that is simple, find length of both lists and their difference, have pointers to the start of both list, increment pointer of longer list by the difference in their length. After this then keep incrementing both by one till they meet.
Hope all of this makes sense.