用单链表做两个链表的交集和并集

用单链表做两个链表的交集和并集

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

typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkedList;

LinkedList LinkedListInit()
{
LinkedList p;
p=(LinkedList)malloc(sizeof(LNode));

p->next=NULL;
return p;
}

LinkedList LinkedListCreat(LinkedList L)
{
int x=0;
LinkedList p,s;

p=L;
printf("输入链表的值，以-1结束\n");
scanf("%d",&x);

while(x!=-1)
{
s=(LinkedList)malloc(sizeof(LNode));
s->data=x;
p->next=s;
p=s;
scanf("%d",&x);
}

p->next=NULL;
return L;
}

void LinkedListTrave(LinkedList L) //ok
{
LinkedList p;
p=L->next;
while(p)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}

LinkedList LinkedListIntersection(LinkedList L1,LinkedList L2,LinkedList L3) // 求交集
{
LinkedList p1,p2,p3;
p1=L1->next,p2=L2->next;
p3=L3;
while(p1)
{
if(p1->data==p2->data)
{
p3->next=p1;
p3=p1;
// p3->next=NULL;
p1=p1->next;
p2=p2->next;
}
else
{
if(p2->next==NULL)
{
p2=L2; //指向L2是为了对应p2=p2->next;能衔接下去
p1=p1->next;
}
p2=p2->next;
}
}
if(p3==NULL) printf("NO Intersection exist\n");
return L3;
}

LinkedList LinkedListMerge(LinkedList L1,LinkedList L2,LinkedList L3) //重复的数字不要,并集
{
LinkedList p1,p2,p3;
p1=L1->next,p2=L2->next;
p3=L3;
while(p1&&p2)
{
if(p1->data>p2->data)
{
p3->next=p2;
p3=p2;
p2=p2->next;
}
else if(p1->data==p2->data)
{
p3->next=p2;
p3=p2;
p2=p2->next;
p1=p1->next;
}
else
{
p3->next=p1;
p3=p1;
p1=p1->next;
}
}
p3->next=p1?p1:p2;
return L3;
}

void main()
{
LinkedList L1,L2,L3;
L1=LinkedListInit(L1);
L2=LinkedListInit(L2);
L3=LinkedListInit(L3);

printf("链表L1的创建\n");
L1=LinkedListCreat(L1);
LinkedListTrave(L1);

printf("链表L2的创建\n");
L2=LinkedListCreat(L2);
LinkedListTrave(L2);

// L3=LinkedListIntersection(L1,L2,L3);
// LinkedListTrave(L3);

L3=LinkedListMerge(L1,L2,L3);
LinkedListTrave(L3);
}