Re: Question on tree-walking and mutually-recursive types

[Locke <riphack at web dot de>]

Hmm, i think i found a very fast version of Tortiose and Hare.
If you have a linked list where every node is connected and you have only one 
edge per node, then if there is a cycle then it must be at the end.
Example:
x1->x2->x3->x1
So you start with the pointer at the first element, x1.
After this you let the pointer step length of list steps forward, the length 
should be known otherwise the algorithm isn't possible in this way (the 
length should _not_ be calculated with a list walkthrough, incrementing while 
adding is more useful).
If the last step succeeds then there must be a cycle.
Problem is that you have to save the number of elements in your list.
With this way a cycle detection in O(n) would be possible, or even O(1) if you 
save a pointer to the last added element of the list.

Ok it has some restrictions but using such a list is not very complicated and 
you onle save one pointer and one integer more than for normal.

cu, Locke