计算一个单项链表（链表中有环）中环的长度-创新互联

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

站在用户的角度思考问题，与客户深入沟通，找到屏南网站设计与屏南网站推广的解决方案，凭借多年的经验，让设计与互联网技术结合，创造个性化、用户体验好的作品，建站类型包括：网站制作、成都网站设计、企业官网、英文网站、手机端网站、网站推广、域名注册、网络空间、企业邮箱。业务覆盖屏南地区。

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

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

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

网站标题：计算一个单项链表（链表中有环）中环的长度-创新互联
文章位置：http://cdkjz.cn/article/dpjhhd.html