Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
That solution works if we are assuming that the loop goes back only to the previous node. If the loop goes back two nodes or three nodes this solution fails to identify the loop.
Here's my solution:
Keep a set of nodes, V, the visited set.
iterate through the linked list, and as you visit a node,
first check if it is already in the visited set.
If it is already in the visited set, you have a loop, return true.
Otherwise, add the node to the visited set.
If you have looped through and never returned true, then there is no loop. return false.
Assuming the list to be singly linked list, after finding the list to be looped as suggested by Mr.scorpion, we keep a pointer in the loop and start another pointer at the start of the list, we keep incrementing the pointer and keep rotating the another pointer which should be pointed to the pointer in the loop by exactly one circle, if we hit the pointer which is walking through the list we found the starting point of the list.
1. Start with 2 pointers at head
2. Move pointer A one node at a time, move pointer B one node at a time
3. If there is a loop, eventually they will meet.
To find the node where the loop starts:
4. After A and B meet, move A back to head.
5. Move both A and B 1 node at a time. They meet at the node where the loop starts.
Detection of the loop:
-------------------------------
Start with two pointers(Fast and slow) at the head.
Fast will move forward fastly(Two nodes at a time)
Slow will move forward slowly(one node at a time)
Slow == Fast => there is a loop in the linked list.
Loop start point:
-------------------------
Let p1 be the node where Fast and Slow are meeting.
Set p2 = p1.
Advance p2 and wait till p2 == p1, Keep on counting the nodes in between. At the end of this we would have the number of nodes(say count) inside the loop.
Now set temp1 = temp2 =head;
move temp2 till count (Number of nodes in the loop)
Now start moving both the pointers (one node at a time)
when temp1 == temp2 (This is the start of the loop)
It should be number of moves.... not number of nodes for the count.....
Well... i have a little confusion... what is considered to be beginning of the loop....
eg: a->b->c->d->e->c...
here beginning of the loop is e or c....
If its c, your solution is correct....
If its e.... a slight modification..... check if temp1->next==temp2.... temp1 is the beginning of the loop.
Below code find the loop in O(n) time with the starting point of the loop
/ *
* Algorithm
* Set node value to INT_MIN as an indicator that node is visited
*
* Recursive go to next node until node is NULL or Node value is INT_MIN
* IF node is NULL then there is no loop
* IF Node value is INT_MIN then node is previously visited and
* the current node is the starting point of loop
*
* While returning reset the node value so that Link List shouldn't alter
*/
struct node {
int value;
struct node *next;
};
typedef struct node * Linklist;
//If there is loop in link list return 0 else return 1
int findLoopInLL(Linklist head, Linklist * start)
{
int result,value;
if(head)
{
if(head->value == INT_MIN)
{
*start = head;
return 0;
}
value = head->value;
head->value = INT_MIN;
result = findLoopInLL(head->next, start);
head->value = value;
return result;
}
start = NULL;
return 1;
}
take to pointer *a and *b.
- scorpion May 21, 20121. start the pointers from head.
2. Move one pointer to one step and other to two step forward
3. when both meets at some point, it concludes that there is loop in the list...