## 問題描述 > 設A和B是兩個單鏈表（帶頭結點），其中元素按遞增有序。設計一個算法從A和B中公共元素產生單鏈表C，要求不破壞A，B的結點 ## 算法思想 > 本算法實際上和[第1章第2節練習題16 歸并并逆序單鏈表](http://blog.csdn.net/u013595419/article/details/50510558)并沒有太大的區別，同樣對兩張鏈表進行遍歷，對于具有相同值的結點進行一次復制，然后將復制出來的新節點采用尾插法建立單鏈表的方式形成新的單鏈表。 ## 算法描述 ~~~ LinkList CreatNew(LNode *head1, LNode *head2, LNode *head) { LNode *p=head1->next; LNode *q=head2->next; LNode *r=head; LNode *L; while(p&&q){ if(p->data==q->data){ L=(LNode*)malloc(sizeof(LNode)); L->data=p->data; r->next=L; r=L; p=p->next; q=q->next; }else if(p->data<q->data){ p=p->next; }else{ q=q->next; } } r->next=NULL; return head; } ~~~ 具體代碼見附件。 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; LinkList CreatList(LNode*); LinkList CreatNew(LNode*,LNode*,LNode*); void Print(LNode*); int main(int argc, char* argv[]) { LNode *head1; head1=(LNode*)malloc(sizeof(LNode)); head1->next=NULL; head1=CreatList(head1); LNode *head2; head2=(LNode*)malloc(sizeof(LNode)); head2->next=NULL; head2=CreatList(head2); LNode *head; head=(LNode*)malloc(sizeof(LNode)); head=CreatNew(head1, head2, head); Print(head1); Print(head2); Print(head); return 0; } //尾插法建立單鏈表 LinkList CreatList(LNode* head) { LNode *L; LNode *r=head; ElemType x; scanf("%d",&x); while(x!=999){ L=(LNode*)malloc(sizeof(LNode)); L->data=x; r->next=L; r=L; scanf("%d",&x); } return head; } //查找公共結點 LinkList CreatNew(LNode *head1, LNode *head2, LNode *head) { LNode *p=head1->next; LNode *q=head2->next; LNode *r=head; LNode *L; while(p&&q){ if(p->data==q->data){ L=(LNode*)malloc(sizeof(LNode)); L->data=p->data; r->next=L; r=L; p=p->next; q=q->next; }else if(p->data<q->data){ p=p->next; }else{ q=q->next; } } r->next=NULL; return head; } //打印所有結點 void Print(LNode *head) { LNode *p=head->next; while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~