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

[Zack Weinberg <zack at codesourcery dot com>]

kenner@vlsi1.ultra.nyu.edu (Richard Kenner) writes:

>     How about the usual two-pointers collapsing loop algorithm to detect
>     the cycle?
>
> Sorry, I don't recognize this reference (and neither does Google).

Like this:

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;
}

zw