【问题描述】

已知两个链表A和B分别表示两个集合，其元素递增排列。请设计一个算法，用于求出A与B的交集，并存放在A链表中。

【参考代码】

typedef struct LNode
{
	int data;
	struct LNode* next;
}LNode, * LinkList;
void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc)
{
	LinkList pa, pb, pc, p;
	pa = La->next;
	pb = Lb->next;
	pc = Lc = La;  //尾插法
	while (pa && pb)
	{
		if (pa->data == pb->data)
		{
			pc->next = pa;
			pc = pa;          //取出相同的元素插入c中
			pa = pa->next;
			p = pb;
			pb = pb->next;
			delete p;        //删除b中相同的元素
		}
		else if (pa->data > pb->data)
		{
			p = pb;
			pb = pb->next;
			delete p;       //删除b中较小的元素
		}
		else
		{
			p = pa;
			pa = pa->next;
			delete p;       //删除a中较小的元素
		}
	}
	while (pa)
	{
		p = pa;
		pa = pa->next;
		delete p;          //删除a中剩余的所有元素
	}
	while (pb)
	{
		p = pb;
		pb = pb->next;
		delete pb;        //删除b中剩余的所有元素
	}
	pc->next = NULL;     //释放头结点
	delete Lb;
}

【代码分析】

此代码针对考研数据结构，所以采用伪代码，主要理解算法处理逻辑，本算法理解起来比较容易，找出data值相同的元素，然后连接到c上，不相同的元素删除。