两个有序链表序列的交集 (20分)
已知两个非降序链表序列S1与S2,设计函数构造出S1与S2的交集新链表S3。
输入格式:
输入分两行,分别在每行给出由若干个正整数构成的非降序序列,用−1表示序列的结尾(−1不属于这个序列)。数字用空格间隔。
输出格式:
在一行中输出两个输入序列的交集序列,数字间用空格分开,结尾不能有多余空格;若新链表为空,输出NULL。
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode {
int Data;
struct LNode *Next;
}List;
int main()
{
List *s1,*s2,*s3,*p1,*p2,*p3;
int x1,x2;
s1 = (List *)malloc(sizeof(List));
s2 = (List *)malloc(sizeof(List));
s3 = (List *)malloc(sizeof(List));
s1->Next = NULL;
s2->Next = NULL;
p1 = s1;
scanf("%d",&x1);
while(x1 != -1)
{
p1->Next = (List*)malloc(sizeof(List));
p1->Next->Data = x1;
p1 = p1->Next;
p1->Next = NULL;
scanf("%d",&x1);
}
scanf("%d",&x2);
p2 = s2;
while(x2 != -1)
{
p2->Next = (List*)malloc(sizeof(List));
p2->Next->Data = x2;
p2 = p2->Next;
p2->Next = NULL;
scanf("%d",&x2);
}
p1 = s1->Next;
p2 = s2->Next;
p3 = s3;
s3->Next = NULL;
while(p1!=NULL&&p2!=NULL)
{
if(p1->Data>p2->Data)
{
p2 = p2->Next;
}
if(p1->Data<p2->Data)
{
p1 = p1->Next;
}
if(p1->Data == p2->Data)
{
p3->Next = p1;
p1 = p1->Next;
p2 = p2->Next;
p3 = p3->Next;
}
p3->Next = NULL;
}
p3 = s3->Next;
if(p3 != NULL)
{
printf("%d",p3->Data);
p3 = p3->Next;
while(p3 != NULL)
{
printf(" %d",p3->Data);
p3 = p3->Next;
}
}
if(s3->Next == NULL)//当s1,s2链表不为空时,s3为空,运行c错误
{
printf("NULL");
}
return 0;
}
当s1,s2链表不为空时,s3为空,交集为空时程序停止工作