速成网站 改版 影响easy wordpress timelines

设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）