已知两个非降序链表序列S1与S2,设计函数构造出S1与S2的交集新链表S3。
输入格式:
输入分两行,分别在每行给出由若干个正整数构成的非降序序列,用−1表示序列的结尾(−1不属于这个序列)。数字用空格间隔。
输出格式:
在一行中输出两个输入序列的交集序列,数字间用空格分开,结尾不能有多余空格;若新链表为空,输出NULL
。
输入样例:
1 2 5 -1
2 4 5 8 10 -1
输出样例:
2 5
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode //链表结构体定义
{
int data;
struct LNode *next;
}LNode,*List;
List read()//创建链表
{
List L,P;
L=(List)malloc(sizeof(List));
L->next=NULL;
P=L;
int a;
while(1)
{
scanf("%d",&a);
if(a==-1)
break;
List q=(List)malloc(sizeof(List));
q->data=a;
q->next=NULL;
P->next=q;
P=q;
}
return L;
}
List merge(List S1,List S2)//取两集合交集
{
List L=(List)malloc(sizeof(List));
List q=L;
L->next=NULL;
S1=S1->next;
S2=S2->next;
while(S1&&S2)
{
if(S1->data==S2->data)//1.S1与S2当前值相等,则取其一,然后都后移
{
q->next=S1;
S1=S1->next;
S2=S2->next;
q=q->next;
}
else if(S1->data<S2->data)//2.S1当前值小于S2当前值,移动S1指针
S1=S1->next;
else//2.S2当前值小于S1当前值,移动S2指针
S2=S2->next;
}
return L;
}
int main()
{
List S1=read();
List S2=read();
List S3=merge(S1,S2);
int flag=0;
S3=S3->next;
while(S3)
{
if(flag)
{
printf(" ");
}
printf("%d",S3->data);
S3=S3->next;
flag=1;
}
if(!flag)
printf("NULL");
return 0;
}