計(jì)算一個(gè)單項(xiàng)鏈表（鏈表中有環(huán)）中環(huán)的長度

    這個(gè)方法用到了快指針和慢指針，他倆從頭結(jié)點(diǎn)一起跑，每次快指針走兩個(gè)節(jié)點(diǎn)，慢指針走一個(gè)節(jié)點(diǎn)，當(dāng)進(jìn)入環(huán)之后，快指針終會(huì)追上慢指針。這時(shí)，記錄相遇的節(jié)點(diǎn)，然后讓慢指針再跑一圈就可以測出環(huán)的長度了。

    這個(gè)方法適用于任何情況，無論整個(gè)鏈表都是環(huán)，還是環(huán)的節(jié)點(diǎn)只有一個(gè)的。

#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
    int num;
    struct node* next;
}NODE;

NODE* create(NODE* phead,int nu)
{
    NODE* tmp = malloc(sizeof(struct node));
    tmp->num = nu;
    NODE* find = phead;
    if(phead == NULL){
        return tmp;
    }
    else{
        while(find->next != NULL)
            find = find->next;
        find->next = tmp;
        return phead;
    }
}

void show(NODE* phead)
{
    int i=0;
    while(i<25){
        printf("%d ",phead->num);
        phead = phead->next;
        i++;
    }
    printf("\n");
#if 0
    while(phead){
        printf("%d ",phead->num);
        phead = phead->next;
    }
    printf("\n");
#endif
}

void createring(NODE* phead, NODE* point)
{
    while(phead->next != NULL)
        phead = phead->next;
    phead->next = point;
}

NODE* point(NODE* phead)
{
    while(phead->next != NULL)
        phead = phead->next;
    return phead;
}

void check(NODE* phead)
{
    NODE* quick = phead;
    NODE* slow = phead;
    NODE* point = NULL;
    NODE* point1 = phead;
    int num = 0;    
    int num1 = 0;
    while(1){
        quick = quick->next->next;    //快指針一次走兩個(gè)
        slow = slow->next;        //慢指針一次走一個(gè)
        if(slow == quick){        
            point = slow;
            point = point->next;    //記錄當(dāng)兩個(gè)指針相遇時(shí)的位置，從這個(gè)位置開始計(jì)數(shù)，當(dāng)指針轉(zhuǎn)一圈時(shí)結(jié)束
            num++;    
            while(slow != point){
                point = point->next;
                num++;
            }
            printf("鏈表中環(huán)的長度為: %d\n",num);
            break;
        }

    }
    while(1){            //當(dāng)快慢指針在環(huán)中相遇時(shí)，一個(gè)新的指針從頭結(jié)點(diǎn)向后走，慢指針繼續(xù)走時(shí)，這兩個(gè)指針就會(huì)相遇在入環(huán)的節(jié)點(diǎn)中。(這個(gè)規(guī)律為什么會(huì)這樣，我也不知道，哪位大神知道，麻煩在評(píng)論區(qū)解釋一下。)
        if(point1 == point)
            break;
        point1 = point1->next;
        point = point->next;
        num1++;
    }
    printf("此鏈表的長度為:%d\n",num1+num);
}

NODE* createlian(NODE* head)
{
    NODE* poin = NULL;
    head = create(head,21);
    create(head,22);
    create(head,23);
    create(head,24);
    create(head,25);
    create(head,26);
    poin = point(head);    //記錄從環(huán)開始的節(jié)點(diǎn)
    create(head,27);
    create(head,28);
    create(head,29);
    create(head,30);
    create(head,31);
    create(head,32);
    create(head,33);
    createring(head,poin);    //讓尾節(jié)點(diǎn)指向環(huán)開始的節(jié)點(diǎn)
    printf("這個(gè)鏈表為：\n");
    show(head);
    return head;
}

int main(void)
{
    
        NODE* head;
    NODE* tail;
       NODE* poin;
        NODE* head1;
    head = createlian(head);    
        check(head);
//        show(head);
        return 0;
}