Subject: Re: Implementation limits when accessing circular lists
From: (Rob Warnock)
Date: Mon, 30 Jun 2003 21:43:32 -0500
Newsgroups: comp.lang.lisp
Message-ID: <>
Tim Daly, Jr. <> wrote:
| "Paul F. Dietz" <> writes:
| > (idea: detect circularity using the standard two pointer trick
| > and use MOD to reduce n to a manageable size.)
| Could someone please clue me in on the "standard two pointer trick"?

Do a web search for:

	tortoise hare circular

or perhaps better:

	tortoise hare "circular list"

Also see CLHS "Function LIST-LENGTH". As shown there, a common approach
is to have the hare move at twice the speed of the tortoise, but many
other winning strategies are possible [iff your termination tests are
correct!]. E.g., make the tortoise move at half the speed of the hare.
[It is useful to ask why/how this might be different than the previous,
and whether or not one might be "better" than the other in some sense.]


Rob Warnock, PP-ASEL-IA		<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607