如何判别一个单链表是否含有回路

codes is included below, this arithmetic is not the best one, but it is the one that easy to be understand. others method not included here, you can google or baidu it for more informations.

-bash-3.2# gcc -o loop_in_list loop_in_list.c
-bash-3.2# ./loop_in_list
NOT LOOP LIST
-bash-3.2# gcc -D_LOOP_LIST -o loop_in_list loop_in_list.c
-bash-3.2# ./loop_in_list
LOOP LIST

/* - loop_in_list.c, not test yet, just for notes - */
#include <stdio.h>
#include <assert.h>

typedef struct node_t{
    int key;
    struct node_t *next;
} node_t;

/*
 * DESC:
 * chk whether 'nd' in the list defined by 'hdr' and 'tail'
 * INPUT:
 * hdr/r: the 1st node pointer
 * tail/r: the last node pointer
 * nd/r: the nd to chk
 * OUTPUT:
 * -1: err
 * 0: no in
 * 1: in
 */
int inlist(node_t *hdr, node_t *tail, node_t *nd)
{
    assert(NULL != hdr);
    assert(NULL != tail);

    if (NULL == nd) return 0;

    for (; hdr != tail; hdr=hdr->next) {
        assert(NULL != hdr);
        /*
        if (NULL == hdr)
            return -1;
        */
        if (nd == hdr)
            return 1;
    }

    /* hdr == tail now */
    if (nd == tail)
        return 1;
   
    return 0;
}

/*
 * DESC:
 * chk whether list has loop nodes
 * INPUT:
 * list/r: the list header
 * OUTPUT:
 * 1: looped
 * 0: it's OK
 */
int loopinlist(node_t *list)
{
    node_t *hdr = list;
    node_t *tail = hdr;
    node_t *cur = NULL;

    assert(NULL != list);

    for (cur=tail->next; NULL!=cur; cur=cur->next) {
        if (inlist(hdr, tail, cur))
            return 1;
        tail = cur;
    }

    return 0;
}

#define LIST_EQ(list, node) \
    (node)->next = (list)->next; \
    (list)->next = (node); \
/*
 * Defines a list to test
 */
int main(void)
{
    int i = 0;
    node_t list[100]; /* not initialized */

    list[0].next = NULL; /* list initialized */
   
    for (i=1; i<100; i++) {
        LIST_EQ(list, &list[i]);
    }

    i = 0;
   
#ifdef _LOOP_LIST
    /* choose a loop */
    list[66].next = &list[55];
    i = loopinlist(list);
#endif
   
    printf("%s\n", (0==i)?"NOT LOOP LIST":"LOOP LIST");

    return 0;
}