从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尾结点指针为空
}