I was asked this question in interview: "How to detect the loop in linked list?", I solved this but immediately the interviewer asked me how do I remove the loop in a linked list. I fumbled.
So any pointers on how to solve this, may be pseudo code, or method definition?
I'm comfortable with Java so I have tagged this question under java.
For Instance this linked list has a loop
0--->1---->2---->3---->4---->5---->6
▲ |
| ▼
11<—-22<—-12<—-9<—-8
Best Answer
There are two parts to this problem:
Once you know where the loop starts, it's easy to identify the last element in the list since it's the element in the list following the start of the loop that ends up pointing back to the start of the loop. It is then trivial to set the next pointer/reference of this element to
null
to correct the cyclic link list (not circular linked list which is where the last elements points back to the first - this would be a specific instance of cyclic lists).Floyd's cycle detect algorithm, also called the tortoise and hare algorithm as it involves using two pointers/references that move at different speeds, is one way of detecting the cycle. If there is a cycle, the two pointers (say
p1
andp2
) will end up pointing to the same element after a finite number of steps. Interestingly, it can be proved that the element at which they meet will be the same distance to the start of the loop (continuing to traverse the list in the same, forward direction) as the start of the loop is to the head of the list. That is, if the linear part of the list hask
elements, the two pointers will meet inside the loop of lengthm
at a pointm-k
from the start of the loop ork
elements to the 'end' of the loop (of course, it's a loop so it has no 'end' - it's just the 'start' once again). And that gives us a way to find the start of the loop:Once a cycle has been detected, let
p2
remain pointing to the element where the loop for the step above terminated but resetp1
so that it's pointing back to the head of the list. Now, move each pointer one element at a time. Sincep2
began inside the loop, it will continue looping. Afterk
steps (equal to the distance of the start of the loop from the head of the list),p1
andp2
will meet again. This will give you a reference to the start of the loop.It is now easy to set
p1
(orp2
) to point to the element starting the loop and traverse the loop untilp1
ends up pointing back to the starting element. At this pointp1
is referencing the 'last' element list and it's next pointer can be set tonull
.Here's some quick and dirty Java code assuming a linked list of
Node
s where aNode
has anext
reference. This could be optimized but it should give you the basic idea:This explanation might help the why behind Part II:
More references: