## 問題描述 > 已知兩個鏈表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"); } ~~~