【数据结构】（单链表）求两个链表的交集

浅浅的花香味﹌ 2021-10-30 00:14 454阅读 0赞

算法思想：其实就是合并链表相同的元素（假设链表有序）

  1. void Union(LinkList &A,LinkList &B){
  4.      if(A->next==NULL||B->next==NULL)
  5.          return ;
  7.      LinkList pa=A->next;
  8.     LinkList pb=B->next;
  9.     LinkList r=A;
  10.     LinkList sa;
  11.     LinkList sb;
  12.     A->next=NULL;
  14.     while(pa&&pb){
  16.         if(pa->data==pb->data){
  18.             sa=pa->next;
  19.             sb=pb->next;
  20.             pa->next=r->next;//尾插法
  21.             r->next=pa;
  22.             r=pa;
  23.             pa=sa;
  24.             free(pb);
  25.             pb=sb;
  26.         }else if(pa->data<pb->data){
  28.             sa=pa->next;
  29.             free(pa);
  30.             pa=sa;
  31.         }else{
  33.             sb=pb->next;
  34.             free(pb);
  35.             pb=sb;
  36.         }
  37.     }
  39.     while(pa){
  41.         sa=pa->next;
  42.         free(pa);
  43.         pa=sa;
  44.     }
  46.     while(pb){
  48.         sb=pb->next;
  49.         free(pb);
  50.         pb=sb;
  51.     }
  53.     free(B);
  54.      r->next=NULL;

发表评论

表情：
评论列表 （有 0 条评论，454人围观）

还没有评论，来说两句吧...

相关阅读

    相关 数据结构-链表之单链表

        单链表即每个节点都存在数据域和指针域（特殊节点除外），每个节点都一个直接前驱节点和直接后继节点（头节点无前驱，尾节点无后继），简单来说就是上一个节点的指针域中存放了下一

    ╰+攻爆jí腚メ╰+攻爆jí腚メ/ 0 赞/ 449 阅读