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

["Dave Korn" <dk at artimi dot com>]

> -----Original Message-----
> From: gcc-owner On Behalf Of Michael Matz
> Sent: 29 June 2004 11:56

> On Tue, 29 Jun 2004, Andreas Schwab wrote:
> 
> > >> struct S { struct S *next; };
> > >> 
> > >> bool
> > >> detect_cycle(struct S *list)
> > >> {
> > >>     struct S *p, *q;
> > >>     bool advance_q = false;
> > >> 
> > >>     if (list == 0)
> > >>       return false;
> > >> 
> > >>     q = list;
> > >>     p = list->next;
> > >> 
> > >>     do
> > >>     {
> > >>         if (q == p)
> > >>             return true;
> > >> 
> > >>         if (advance_q)
> > >>             q = q->next;
> > >>         p = p->next;
> > >>         advance_q = !advance_q;
> > >>     }
> > >>     while (p);
> > >>     return false;
> > >> }

> ???  Zack's loop is "do {} while (p);".  It stops after p 
> traversed the
> list exactly once (after which q has traversed it half way).

  That's only if the list doesn't contain a loop, of course.  If the list
does contain a loop (the condition we're trying to detect, after all) then
do while (p) will continue forever.  At that point the problem becomes
returning TRUE from the function in anything less than an infinite amount of
time...

>  Also
> different speeds are not guaranteeing that all elements would 
> be compared.  
> For that the steps would have to be relative prime to the list length.

  The increments of p and q need to be relatively prime to each other, but
not to the list length: that doesn't matter.
 
> And if one does that at all, then why not simply two nested 
> loops (the 
> inner starting with the element pointing after the one from outer)?

  This is a very standard problem.  I got asked it in my most recent job
interview.

http://www.google.com/search?hl=en&lr=&ie=UTF-8&q=detect+cycle+linked+list

Oh look, it's called the "Tortoise and Hare" technique!

http://c2.com/cgi/wiki?TortoiseAndHare

  And the usual solution involves advancing p by one link and q by two links
at each step.  Off the top of my head, I'd think this was equivalent to two
iterations of (advancing p on alternate steps and advancing q every step),
but that would seem to me to take twice as many iterations and tests,
unneccessarily.


    cheers, 
      DaveK
-- 
Can't think of a witty .sigline today....