## 问题描述 > 已知两个链表A和B分别表示两个集合，其元素递增排列。编写函数，求A与B的交集，并存放于A链表中 ## 算法思想 > 本题算法实际和 [ 第1章第2节练习题17 使用相同值结形成新单链表 ](http://blog.csdn.net/u013595419/article/details/50510681)并无太大区别，但是也应注意到本题中明确要求对单链表A进行拆分，仅仅保留单链表A和单链表B中结点数据域相同的部分，既然这样，我们便可以对单链表A和单链表B分别设置两个指针进行遍历，删除数据域中单链表A中有的，而单链表B中没有的结点便可。算法描述如下： ## 算法描述 ~~~ LinkList Intersection(LNode *head1, LNode *head2) { LNode *prep=head1; LNode *p=head1->next; LNode *q=head2->next; while(p&&q){ if(p->data==q->data){ prep=p; p=p->next; q=q->next; }else if(p->data<q->data){ prep->next=p->next; free(p); p=prep->next; }else{ q=q->next; } } //若单链表B已经遍历已完成，而A仍有剩余，删除单链表A中的所有结点 while(p){ prep->next=p->next; free(p); p=prep->next; } return head1; } ~~~ 具体代码见附件。 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; LinkList CreatList(LNode*); LinkList Intersection(LNode*,LNode*); void Print(LNode*); int main(int argc,char* argv[]) { LNode *head1; head1=(LNode*)malloc(sizeof(LNode)); head1=CreatList(head1); LNode *head2; head2=(LNode*)malloc(sizeof(LNode)); head2=CreatList(head2); Print(head1); Print(head2); head1=Intersection(head1, head2); Print(head1); return 0; } //尾插法建立单链表 LinkList CreatList(LNode *head) { LNode *r=head; LNode *L; ElemType x; scanf("%d",&x); while(x!=999){ L=(LNode*)malloc(sizeof(LNode)); L->data=x; r->next=L; r=L; scanf("%d",&x); } r->next=NULL; return head; } //查找数据域的值相同的结点 LinkList Intersection(LNode *head1, LNode *head2) { LNode *prep=head1; LNode *p=head1->next; LNode *q=head2->next; while(p&&q){ if(p->data==q->data){ prep=p; p=p->next; q=q->next; }else if(p->data<q->data){ prep->next=p->next; free(p); p=prep->next; }else{ q=q->next; } } while(p){ prep->next=p->next; free(p); p=prep->next; } return head1; } //打印全部结点 void Print(LNode *head) { LNode *p=head->next; while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~