链表相交及求其交点

题目：
判断两个链表是否相交， 如果相交， 计算交点

 void find_two_list_intersection(pstu head1, pstu head2) {
     int len1, len2;  
     pstu pcur1=NULL, pcur2=NULL;
     pstu tail1 = head1, tail2 = head2;
     while (tail1)            
     {
         len1++;
         pcur1 = tail1;
         tail1 = tail1->pnext;
     }
     while (tail2)
     {
         len2++;
         pcur2 = tail2;
         tail2 = tail2->pnext;
     }
     if (pcur1 == pcur2)         //若尾指针相同则相交
     {
         pstu p = len1 > len2 ? head1 : head2;           //p指向较长链表的头节点
         for (int i = 0; i < abs(len1 - len2); i++)    //p先前进的步数等于两链表的差值
         {
             p = p->pnext;
         }
         pstu p1 = len1 > len2 ? head1 : head2;  //p1指向较短链表的头节点
         while (p != p1)           //p和p1同时前进，相同则为两链表的交点
         {
             p = p->pnext;
             p1 = p1->pnext;
         }
         printf("The intersection is:%dn", p1->num);
     } else {     
         printf("there isn't an intersection;");
     }
 }

也可使链表尾结点指向某一链表头节点，判断另一条链表是否有环

 void isloope(pstu head)
 {
     pstu slow=head, fast=head;
     while (fast && fast->pnext)
     {
         slow = slow->pnext;       //slow每次走一步
         fast = fast->pnext->pnext;//fast每次走两步
         if (fast == slow)  //若fast追上slow则有环，且一定是在环上追上slow
         {
             printf("there is a loope");
             return;
         }
     }
      printf("there isn't a loope");
}

最后

以上就是简单短靴为你收集整理的链表相交及求其交点的全部内容，希望文章能够帮你解决链表相交及求其交点所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。