### loop in a linked list

The problem is: Given an uni-directional linked list, detect infinite loop without using any extra data structure.

The linked list data structure is really simple:

class Node {

Node next;

}

The linked list data structure is really simple:

class Node {

Node next;

}

Turtle and rabbit race:

ReplyDeleteboolean isInInfiniteLoop(Node node) {

if (node == null) {

return false;

}

Node turtle = node; // slower moving node

Node rabbit = node.next; // faster moving node

while (rabbit != null) {

if (rabbit.equals(turtle)) {

// the faster moving node has caught up with the slower moving node

return true;

} else if (rabbit.next == null) {

// reached the end of list

return false;

} else {

turtle = turtle.next;

rabbit = rabbit.next.next;

}

}

// rabbit reached the end

return false;

}

what if you have to make a new linked list with all the nodes in the loop and that too without a loop? the root is the first node found during the left traversal.

ReplyDeleteCan u give an algorithm to detect where the looping begins? Finding loop in a linked list is very familiar problem.Bt I couldnt find an algorithm to detect the node where the looping begins.If u can it will be very helpful...Thanks in advance..

ReplyDeleteas soon as the condition if (rabbit.equals(turtle)) gets satisfied it means there is loop in linked list.

ReplyDeleteNow to find the node where loop starts.

1)Take a pointer at first node.

2)start moving one step from the node where loop condition is satisfied.

3)Node where both nodes are equal then that is the required node.

are you traversing two ways- one within the loop and one from the beginning?

ReplyDeleteIf that is the case, then they can meet anywhere inside the loop.Please let me know if i hv not understood it well.

To find the loop point , i hv an algorithm with O(n^2) time complexity and O(n)space complexity.It is as:

1.reverse the linked list, if we can reach at the root node back before reaching null, then there is a loop.

Now to find the point of loop, perform the following:

2.copy this linked list.

3.reverse the copied list to get the original ll.

4.traverse both the linked list simultaneously. The point where the next node reference of the two ll differ is the point of the loop.

can you suggest someway of reducing the complexity this way or the other?

yeah you are right we are traversing two ways one from the point inside loop where two pointer meets and one from starting node.

ReplyDeleteyou can better verify with one example then comment if not clear..:)

thanks...very efficient method...never thought that way.

ReplyDeletethnx..:)

ReplyDeletep=head;

ReplyDeleteq=head->next;

while(p!=NULL && q!=NULL)

{

if(p==q)

{

//Loop detected!

exit(0);

}

p=p->next;

q=(q->next)?(q->next->next):q->next;

}

// No loop.