7-52 两个有序链表序列的交集 C语言
程序员文章站
2022-06-07 21:44:46
...
已知两个非降序链表序列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 list* List;
struct list{
int data;
List next;
};
int main()
{
int i,n,flag = 0;
List s1,s2,s3,t,S1,S2,S3;
S1 = (List)malloc(sizeof(struct list));
S2 = (List)malloc(sizeof(struct list));
S3 = (List)malloc(sizeof(struct list));
S3->next = NULL;
s1 = S1;
s2 = S2;
s3 = S3;
/* 往s1里输入数据 */
while(1){
scanf("%d",&n);
if(n == -1) break;
t = (List)malloc(sizeof(struct list));
t->data = n;
t->next = NULL;
s1->next = t;
s1 = s1->next;
}
/* 往s2里输入数据 */
while(1){
scanf("%d",&n);
if(n == -1) break;
t = (List)malloc(sizeof(struct list));
t->data = n;
t->next = NULL;
s2->next = t;
s2 = s2->next;
}
s1 = S1;
s2 = S2;
/* 判断交集并输入进s3 */
while(s1->next != NULL && s2->next != NULL){
if(s1->next->data == s2->next->data){
s3->next = s1->next;
s1 = s1->next;
s2 = s2->next;
s3 = s3->next;
}else if(s1->next->data > s2->next->data){
s2 = s2->next;
}else{
s1 = s1->next;
}
}
/* 输出 */
s3 = S3;
if(s3->next == NULL){
printf("NULL");
return 0;
}
while(s3->next != NULL){
if(!flag){
flag = 1;
printf("%d",s3->next->data);
}else{
printf(" %d",s3->next->data);
}
s3 = s3->next;
}
}