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.
|Email:||(Your email is not shared with anybody)|