设A和B是两个单链表(带头节点),其中元素递增有序。设计一个算法从A到B的公共元素产的C表(交集),要求不破坏A,B的节点。
思想:依次比较A,B表中的元素,相同时,尾插法插入到表中。若不等,将较小的指针后移,知道其中一个链表遍历到表尾。
代码:
LinkList Get_Come(LinkList A,LinkList B){LNode *p=A->next,*q=B->next;//p表示表A子表,q表示表B子表 LinkList C =(LinkList)malloc(sizeof(LNode));LNode *r=C,*s;while(p!=NULL && q!=NULL){//子表均有子表 if(p->data==q->data){//相同元素时,利用尾巴插法插入到C表中 s=(LNode*)malloc(sizeof(LNode));s->data=q->data;r->next=s;r=s;//向后遍历 p=p->next;q=q->next;}else if(p->data<q->data){//A表中的数据更小时,因表是递增有序,所以将A表往后遍历 p=p->next; }else{q=q->next; //B表中的数据更小时,因表是递增有序,所以将B表往后遍历 }} r->next=NULL;//表C的表尾置空 return C;
}
时间复杂度O(m+n);空间复杂度O(min(m,n)