Question on tree-walking and mutually-recursive types

[Michael Matz]

Hi,

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;
> >> }
> >
> > ???  This tests if list_{2j+1} or list_{2j+2} equals list_j.  Hence it 
> > doesn't detect cycles.  Cf list == {1,2,3,1}
> 
> It doesn't have to detect it in the first round, but eventually the
> pointers will be equal in some other round since they are running at
> different speeds through the cycle.

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

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)?


Ciao,
Michael.