从A和B两个单链表的公共元素中产生单链表C
问题描述:
设A和B是两个单链表(带头结点),其中元素递增有序。设计一个算法从A和B 中公共元素产生单链表C,要求不破坏A、B的结点。
问题解答:
算法思想:尾插法建立单链表C,由于算法要求不破坏A、B的结点,所以,需要通过比较复制的方式产生单链表C。
void Get_Common (LinkList A, linkList B) {
//本算法产生单链表A和B的公共元素的单链表C
LNode *p=A->next,*q=B->next,*r,*s;
LinkList C=(LinkList)malloc(sizeof(LNode)) ; //建立表 C
r=C; //r始终指向C的尾结点
while (p!=NULL && q!=NULL) { //循环跳出条件
if(p->data<q->data)
p=p->next; //若A的当前元素较小,后移指针
else if(p->data>q->data)
q=q->next; //若B的当前元素较小,后移指针
else{ //找到公共元素结点
s=(LNode *)malloc(sizeof(LNode));
s->data=p->data; // 复制产生结点 * s
r->next=s; r=s; //将*s链接到C上(尾插法)
p=p->next; //表A和B继续向后扫描
q=q->next;
}
}
r->next=NULL; //置C尾结点指针为空
}