第1章第2节练习题18 求两个单链表的交集
最后更新于：2022-04-01 19:51:16
## 问题描述
> 已知两个链表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->datadata){
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
#include
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->datadata){
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");
}
~~~
';