Say you have a linked list structure in Java. It's made up of Nodes:
class Node {
Node next;
// some user data
}
and each Node points to the next node, except for the last Node, which has null for next. Say there is a possibility that the list can contain a loop - i.e. the final Node, instead of having a null, has a reference to one of the nodes in the list which came before it.
What's the best way of writing
boolean hasLoop(Node first)
which would return true
if the given Node is the first of a list with a loop, and false
otherwise? How could you write so that it takes a constant amount of space and a reasonable amount of time?
Here's a picture of what a list with a loop looks like:
You can make use of Floyd's cycle-finding algorithm, also known as tortoise and hare algorithm.
The idea is to have two references to the list and move them at different speeds. Move one forward by 1
node and the other by 2
nodes.
next
)
will become null
.Java function implementing the algorithm:
boolean hasLoop(Node first) {
if(first == null) // list does not exist..so no loop either
return false;
Node slow, fast; // create two references.
slow = fast = first; // make both refer to the start of the list
while(true) {
slow = slow.next; // 1 hop
if(fast.next != null)
fast = fast.next.next; // 2 hops
else
return false; // next node null => no loop
if(slow == null || fast == null) // if either hits null..no loop
return false;
if(slow == fast) // if the two ever meet...we must have a loop
return true;
}
}