What's the best (halting) algorithm for determining if a linked list has a cycle in it?
[Edit] Analysis of asymptotic complexity for both time and space would be sweet so answers can be compared better.
[Edit] Original question was not addressing nodes with outdegree > 1, but there's some talk about it. That question is more along the lines of "Best algorithm to detect cycles in a directed graph".
What about using a hash table to store the already seen nodes (you look at them in order from the start of the list)? In practise, you could achieve something close to O(N).
Otherwise, using a sorted heap instead of a hash table would achieve O(N log(N)).
Have two pointers iterating through the list; make one iterate through at twice the speed of the other, and compare their positions at each step. Off the top of my head, something like:
node* tortoise(begin), hare(begin);
while(hare = hare->next)
{
if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
hare = hare->next;
if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
tortoise = tortoise->next;
}
O(n), which is as good as you can get.
I wonder if there's any other way than just going iteratively - populate an array as you step forwards, and check if the current node is already present in the array...
You think overly complicated. Just test whether you've reached the beginning:
What if your damaged list is: A -> B -> C -> D -> B -> ... ?
You'll never return to the beginning.
Konrad Rudolph's algorithm won't work if the cycle isn't pointing to the beginning. The following list will make it an infinite loop: 1->2->3->2.
DrPizza's algorithm is definitely the way to go.
In this case OysterD's code will be the fastest solution (vertex coloring)
That would really surprise me. My solution makes at most two passes through the list (if the last node is linked to the penultimate lode), and in the common case (no loop) will make only one pass. With no hashing, no memory allocation, etc.
In this case OysterD's code will be the fastest solution (vertex coloring)
That would really surprise me. My solution makes at most two passes through the list (if the last node is linked to the penultimate lode), and in the common case (no loop) will make only one pass. With no hashing, no memory allocation, etc.
Yes. I've noticed that the formulation wasn't perfect and have rephrased it. I still believe that a clever hashing might perform faster – by a hair. I believe your algorithm is the best solution, though.
Just to underline my point: the vertec coloring is used to detect cycles in dependencies by modern garbage collectors so there is a very real use case for it. They mostly use bit flags to perform the coloring.
@Konrad:34296
The turtle/hare solution only works for a linked list with one child per parent. I think the big difference to GC is that you have a tree with potential cycles as well, for which DrPizzas solution will not work.
But those are two different problems.
Yes, I can imagine that for something like an arbitrary graph where iteration is relatively expensive and cycles are expected then you might well want to use some alternative mechanism (especially if you could do something like encode marked/not marked into the low bit of each pointer).
You will have to visit every node to determine this. This can be done recursively. To stop you visiting already visited nodes, you need a flag to say 'already visited'. This of course doesn't give you loops. So instead of a bit flag, use a number. Start at 1. Check connected nodes and then mark these as 2 and recurse until the network is covered. If when checking nodes you encounter a node which is more than one less than the current node, then you have a cycle. The cycle length is given by the difference.