C/C++経典面接問題の判断チェーンテーブルにループがあるかどうか

#include <cstdio>

typedef struct list
{
    int data;
    struct list *next;
}LIST;

/* Method 1: check the occurrence of p->next from head to p */
bool check_circle_1(LIST *head)
{
    LIST *p = head, *q= NULL;

    if (p == NULL)
        return false;

    while (p->next)
    {
        /* check whether p points to itself */
        if (p->next == p)
        {
            return true;
        }

        /* check the occurrence of p->next in head to p */
        q = head;
        while (q != p)
        {
            if (q == p->next)
            {
                return true;
            }
            q = q->next;
        }
        p = p->next;
    }
    /* p->next is NULL, not a circle */
    return false;
}

/* Method 2: q goes faster than p, if at last p == q, means there's circle */
/*   ：     。   ：               */
bool check_circle_2(LIST *head)
{
    LIST *p, *q;
    p = head;

    if (p == NULL)
        return false;

    q = p->next;

    while (p != NULL && q != NULL)
    {
        if (p == q)
        {
            return true;
        }
        p = p->next;
        if (q->next == NULL)
        {
            return 0;
        }
        else
        {
            q=q->next->next;
        }
    }
    return 0;
}
void testIS()
{
    LIST a, b, c, *head = &a;
    a.next = &b;
    b.next = &c;
    c.next = &a;
    printf("1:is circle | 0:not circle || result check_circle_1(head):\
        %d
", check_circle_1(head));
    printf("1:is circle | 0:not circle || result check_circle_1(head):\
        %d
", check_circle_2(head));
}
void testNO()
{
    LIST a, b, c, *head = &a;
    a.next = &b;
    b.next = &c;
    c.next = NULL;
    printf("1:is circle | 0:not circle || result check_circle_1(head):\
        %d
", check_circle_1(head));
    printf("1:is circle | 0:not circle || result check_circle_1(head):\
        %d
", check_circle_2(head));
}
int main()
{
    printf("-------testIS()--------
");
    testIS();
    printf("-------testNO()--------
");
    testNO();
}
/****************************************
        ：
-------testIS()--------
1:is circle | 0:not circle || result check_circle_1(head):        1
1:is circle | 0:not circle || result check_circle_1(head):        1
-------testNO()--------
1:is circle | 0:not circle || result check_circle_1(head):        0
1:is circle | 0:not circle || result check_circle_1(head):        0

Process returned 0 (0x0)   execution time : 0.078 s
Press any key to continue.

*****************************************/

#include typedef struct list {     int data;     struct list *next; }LIST; /* Method 1: check the occurrence of p->next from head to p */bool check_circle_1(LIST *head) {     LIST *p = head, *q= NULL;     if (p == NULL)         return false;     while (p->next)     {        /* check whether p points to itself */        if (p->next == p)         {             return true;         }        /* check the occurrence of p->next in head to p */        q = head;         while (q != p)         {             if (q == p->next)             {                 return true;             }             q = q->next;         }         p = p->next;     }    /* p->next is NULL, not a circle */    return false; } /* Method 2:q goes faster than p,if at last p==q,means there's circle*//*の利点:論理的に簡単です.短所:どの点から外すか分からない*/bool check_circle_2(LIST *head) {     LIST *p, *q;     p = head;     if (p == NULL)         return false;     q = p->next;     while (p != NULL && q != NULL)     {         if (p == q)         {             return true;         }         p = p->next;         if (q->next == NULL)         {             return 0;         }         else         {             q=q->next->next;         }     }     return 0; } void testIS() {     LIST a, b, c, *head = &a;     a.next = &b;     b.next = &c;     c.next = &a;     printf("1:is circle | 0:not circle || result check_circle_1(head):\        %d", check_circle_1(head));     printf("1:is circle | 0:not circle || result check_circle_1(head):\        %d", check_circle_2(head)); } void testNO() {     LIST a, b, c, *head = &a;     a.next = &b;     b.next = &c;     c.next = NULL;     printf("1:is circle | 0:not circle || result check_circle_1(head):\        %d", check_circle_1(head));     printf("1:is circle | 0:not circle || result check_circle_1(head):\        %d", check_circle_2(head)); } int main() {     printf("-------testIS()--------");     testIS();     printf("-------testNO()--------");     testNO(); }/**************************************** プログラムの実行結果は、次のとおりです.------testIS()------1:is circle|0:not circle|result check_circle_1(head):        1 1:is circle | 0:not circle || result check_circle_1(head):        1 -------testNO()-------- 1:is circle | 0:not circle || result check_circle_1(head):        0 1:is circle | 0:not circle || result check_circle_1(head):        0 Process returned 0 (0x0)   execution time : 0.078 s Press any key to continue.
*****************************************/