Given a singly linked list with a loop ......

Interview Questions

Microsoft Interview Questions and Answers

23. Given a singly linked list with a loop ......

Question:
Given a singly linked list with a loop. Find exact location (the element number) where the loop starts. Obviously, using O(1) space (this also means you are not allowed to associate any data with the list elements)

maybe an answer1:

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. */
}
}

maybe an answer2:

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,

maybe an answer3:

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;
}

(Continued on next question...)