求两个递增链表A和B的交集，并将结果放在链表A中

问题描述：

已知两个链表A和B分别表示两个集合，其元素递增排列。编制函数，求A与B 的交集，并存放于A链表中。

问题解答：

算法思想：釆用归并的思想，设置两个工作指针pa和pb，对两个链表进行归并扫描，只有同时出现在两集合中的元素才链接到结果表中且仅保留一个，其他的结点全部释放。当一个链表遍历完毕后，释放另一个表中剩下的全部结点。

LinkList Union(LinkList &la,LinkList &lb) {
    pa=la->next;  //设工作指针分别为pa和pb
    pb=lb->next;
    pc=la;  //结果表中当前合并结点的前驱指针
    while(pa&&pb){
        if(pa->data==pb->data) {  //交集并入结果表中
            pc->next=pa;    //A中结点链接到结果表
            pc=pa;
            pa=pa->next;
            u=pb;  //B中结点释放
            pb=pb->next;
            free(u);
        }
        else if (pa->data<pb->data) { //若A中当前结点值小于B中当前结点值
            u=pa;
            pa=pa->next;  //后移指针
            free(u) ; //释放A中当前结点
        }else{  //若B中当前结点值小于A中当前结点值
            u=pb;
            pb=pb->next;  //后移指针
            free (u) ;  //释放B中当前结点
        }
    }  //while 结束
    while(pa){    //B已遍历完，A未完
        u=pa;
        pa=pa->next;
        free (u) ;  //释放A中剩余结点
    }
    while(pb){  //A已遍历完，B未完
        u=pb;
        pb=pb->next;
        free(u) ; //释放B中剩余结点
    }
    pc->next=NULL;    //置结果链表尾指针为NULL
    free (lb) ;    //释放B表的头结点
    return la;
}

链表归并类型的题在各学校历年真题中出现的频率很高，故应扎实掌握此类问题的思想。该算法的时间复杂度为O(len1+len2)，空间复杂度为O(1)。