计算一个单项链表（链表中有环）中环的长度

这个方法用到了快指针和慢指针，他俩从头结点一起跑，每次快指针走两个节点，慢指针走一个节点，当进入环之后，快指针终会追上慢指针。这时，记录相遇的节点，然后让慢指针再跑一圈就可以测出环的长度了。

创新互联公司成立以来不断整合自身及行业资源、不断突破观念以使企业策略得到完善和成熟，建立了一套“以技术为基点，以客户需求中心、市场为导向”的快速反应体系。对公司的主营项目，如中高端企业网站企划 / 设计、行业 / 企业门户设计推广、行业门户平台运营、app软件开发、成都手机网站制作、微信网站制作、软件开发、成都温江机房等实行标准化操作，让客户可以直观的预知到从创新互联公司可以获得的服务效果。

这个方法适用于任何情况，无论整个链表都是环，还是环的节点只有一个的。

#include
#include

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;    //快指针一次走两个
        slow = slow->next;        //慢指针一次走一个
        if(slow == quick){
            point = slow;
            point = point->next;    //记录当两个指针相遇时的位置，从这个位置开始计数，当指针转一圈时结束
            num++;
            while(slow != point){
                point = point->next;
                num++;
            }
            printf("链表中环的长度为: %d\n",num);
            break;
        }

    }
   while(1){           //当快慢指针在环中相遇时，一个新的指针从头结点向后走，慢指针继续走时，这两个指针就会相遇在入环的节点中。(这个规律为什么会这样，我也不知道，哪位大神知道，麻烦在评论区解释一下。)
       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);    //记录从环开始的节点
    create(head,27);
    create(head,28);
    create(head,29);
    create(head,30);
    create(head,31);
    create(head,32);
    create(head,33);
    createring(head,poin);    //让尾节点指向环开始的节点
    printf("这个链表为：\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;
}

文章名称：计算一个单项链表（链表中有环）中环的长度
标题路径：http://cdiso.cn/article/gghjhs.html

计算一个单项链表（链表中有环）中环的长度

其他资讯