当前位置：首页 > article >正文

A表和B表公共元素产生链表C

article 2024/12/21 19:58:11

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

查看全文

http://www.kler.cn/a/299164.html