- 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
slow
andfast
) 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
fast
remain pointing to the element where the loop for the step above terminated but resetslow
so that it’s pointing back to the head of the list. Now, move each pointer one element at a time. Sincefast
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),slow
andfast
will meet again. This will give you a reference to the start of the loop. - It is now easy to set
slow
(orfast
) to point to the element starting the loop and traverse the loop untilslow
ends up pointing back to the starting element. At this pointslow
is referencing the ‘last’ element list and it’s next pointer can be set tonull
.
Implementation
public static LinkedListNode lastNodeOfTheLoop(LinkedListNode head) {
LinkedListNode slow = head;
LinkedListNode fast = head;
// find meeting point using Tortoise and Hare algorithm
// this is just Floyd's cycle detection algorithm
while (fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
// Error check - there is no meeting point, and therefore no loop
if (fast.next == null) {
return null;
}
slow = head;
// Until both the references are one short of the common element which is the start of the loop
while (slow.next != fast.next) {
slow = slow.next;
fast = fast.next;
}
// Now fast points to the start of the loop (inside cycle).
return fast;
}
LinkedListNode lastNodeOfTheLoop = findStartOfLoop(head);
lastNodeOfTheLoop.next = null; // or lastNodeOfTheLoop.next = head;