Make delicious recipes!

Find loop in linked list and remove the loop


To remove the loop, we need to find the node at which the loop begins.

Detection is easy by using fast and normal pointers (referred to as FP and NP from now on) to traverse such that the fast pointer traverses 2 nodes while normal pointer moves 1 node at a time. If they meet, then there is a loop.


To find the loop length, move FP and NP once again till they meet.

If loop is of length k, FP and NP will meet again after NP has moved k/2 nodes and FP has moved k nodes.

To find the loop beginning, take two pointers from the list beginning but separated by k nodes. At that time, the first pointer is N-k node from the loop beginning and second pointer is N-k from the loop end. So if we move them till they meet, then they will meet after N-k nodes i.e. at the loop beginning.



Examples:






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal