PRG2.求两个单链表的交集

设计一个函数 void Intersection(List La, List Lb) , 其功能是求Lb和La的交集，且将交集的结果置于La中，其中La和Lb的元素均为严格递增有序排列，求交集后的La的元素也为严格递增有序排列。La和Lb是带头结点的单向链表。

#include <stdio.h>
#include <stdlib.h>

//设计一个函数
/*void  Intersection(List La, List Lb)
其功能是求Lb和La的交集，且将交集的结果置于La中，其中La和Lb的元素均为严格递增有序排列，求交集后的La的元素也为严格递增有序排列。La和Lb是带头结点的单向链表。*/
//其中List是如下结构体：
typedef struct T_Node {//结点类型定义
	int d;//结点中的数据data
	struct T_Node* next;//指向下一个结点的指针
} Node, * List;
//函数中，不得生成新的结点，尽量利用已经有的结点。

void Intersection(List La, List Lb)
{
	Node* pre = La;//指针pre指向头结点
	Node* p1 = La->next;//指针p1指向首元结点
	Node* p2 = Lb->next;//指针p2指向首元结点

	while (p1 != NULL && p2 != NULL)//当两个链表均不为空时
	{
		if (p1->d == p2->d)//如果指针p1、p2分别指向的结点的值想等
		{
			pre = p1;//指针pre指向指针p1所指的结点
			p1 = p1->next;//指针p1后移一位
			p2 = p2->next;//指针p2后移一位
		}
		else if (p1->d > p2->d)//如果指针p1所指的结点的值大于指针p2所指的结点的值
		{
			do {
				p2 = p2->next;//指针p2后移
			} while (p2 != NULL && p1->d > p2->d);//当指针p2所指的结点不为空或者指针p1所指的结点的值大于指针p2所指的结点的值时
		}
		else//或者即指针p1所指的结点的值小于指针p2所指的结点的值
		{
			do {
				p1 = p1->next;//指针p1后移一位
				free(pre->next);//释放指针pre的next结点
				pre->next = p1;//将指针p1所指结点链接到指针pre所指结点后
			} while (p1 != NULL && p1->d < p2->d);//当指针p1所指结点不为空或者指针p1所指结点的值小于指针p2所指结点时
		}
	}

	if (p1 != NULL)//如果指针p1所指结点不为空，即La链表尚未遍历完
	{
		do {
			p1 = p1->next;//指针p1后移一位
			free(pre->next);//释放此时指针pre的next结点
			pre->next = p1;//将指针p1所指结点链接到指针pre所指结点之后
		} while (p1 != NULL);//当指针p1所指结点不为空时
	}
}

//创建头指针为la, lb的两个链表
void createlink(List* pla, List* plb)
{
	int i;
	Node* p;

	*pla = (Node*)malloc(sizeof(Node));     //创建头结点
	p = *pla;

	for (i = 1; i <= 10; i++)
	{
		p->next = (Node*)malloc(sizeof(Node));
		p = p->next;
		p->d = i * 2;
		p->next = NULL;
	}


	*plb = (Node*)malloc(sizeof(Node));     //创建头结点
	p = *plb;

	for (i = 1; i <= 8; i++)
	{
		p->next = (Node*)malloc(sizeof(Node));
		p = p->next;
		p->d = i + 6;
		p->next = NULL;
	}
}

//如下的main函数执行后
void main()
{
	int i;

	List la, lb;
	Node* p;

	createlink(&la, &lb);
	Intersection(la, lb);
	p = la->next;
	
	while (p != NULL)
	{
		printf("%4d", p->d);
		p = p->next;
	}
	printf("\n");
}
/*执行的结果为
8  10  12  14*/