detecting the start of a loop in a singly linked link list?

Question

Is there any way of finding out the start of a loop in a link list using not more than two pointers? I do not want to visit every node and mark it seen and reporting the first node already been seen.Is there any other way to do this?

Answer 1

Here you can find the answer.. http://www.cpp-programming.net/c-tidbits/detecting-a-loop-in-single-linked-list/

Answer 2

There are two way to find the loops in a link list. 1. Use two pointer one advance one step and other advance two steps if there is loop, in some point both pointer get the same value and never reach to null. But if there is no loop pointer reaches to null in one point and both pointer never get the same value. But in this approach we can get there is a loop in the link list but we can't tell where exactly starting the loop. This is not the efficient way as well.

1. Use a hash function in such a way that the value should be unique. Incase if we are trying to insert the duplicate it should through the exception. Then travel through each node and push the address into the hash. If the pointer reach to null and no exception from the hash means there is no cycle in the link list. If we are getting any exception from hash means there is a cycle in the list and that is the link from which the cycle is starting.

Answer 3

Proceed in the usual way u'll use to find the loop. ie. Have two pointers, increment one in single step and other in two steps, If they both meet in sometime, there is a loop. Next step, freeze one pointer where it was and increment the other pointer in one step counting the steps u make and when they both meet again, the count will give u the length of the loop. Next step, reset both pointers to the start of the link list, increment one pointer to the length of loop times and then start the second pointer. increment both pointers in one step and when they meet again, it'll be the start of the linked list.