Interview question: How do I detect a loop in this linked list?
Posted
by jjujuma
on Stack Overflow
See other posts from Stack Overflow
or by jjujuma
Published on 2010-04-18T17:08:53Z
Indexed on
2010/04/19
2:13 UTC
Read the original article
Hit count: 258
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:
Node->Node->Node->Node->Node->Node--\
\ |
----------------
© Stack Overflow or respective owner