Noah Friedman <xxxxxx@splode.com> writes:

 > But since a couple of people made remarks on this list to effect
 > that this looked like an "expensive" problem, I just wanted to
 > point out that it's not especially so.

Its complexity isn't higher, but it's still more work.  You have two
additional variables you're maintaining & and two additional tests per
loop.  It's not clear whether the extra work is worth it.  Its cost
on lists with loops ends up being proportional to 2 * (length up to
loop) + (2 or 3) * length of loop (depending on how many times the
loop is initially traversed).

Incidentally, another algorithm for length which doesn't go into an
infinite loop on circular lists is to reverse the pointers as you walk
the list.  If you get back to the head then you encountered a circular
list.  This one ends up (for lists with loops) being proportional to 4
* (length up to loop) + 2 * length of loop.  But I wouldn't recommend
it for lots of reasons...

--
Harvey Stein
Bloomberg LP
xxxxxx@bloomberg.net