7-5 两个有序链表序列的交集 (20分) 已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。 输入格式: 输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−
32进制 2020-09-08 00:07:41
1 收藏
分类专栏： 陆军工程大学数据结构MOOC习题集（2020秋）
7-5 两个有序链表序列的交集 (20分)
已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。
输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。
在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。
125-1
245810-1
25
#include"stdio.h"
#include"math.h"
#defineN 100000
typedefstructlinknode
{
intdata;
structlinknode*next;
}node,*ptr;
intmain(){
ptr s1,s2,s3,p,q,z,last;
intx;
s1 =NULL;
s2=NULL;
s3=NULL;
/* 前向插入
while (x>=0) {
p=(ptr)malloc(sizeof(node));
p->data=x;
//前向插入足矣
p->next=head;
head=p;
scanf("%d",&x);
}*/
//后向插入方法
scanf("%d",&x);
while(x>=0){
p=(ptr)malloc(sizeof(node));
p->data=x;
if(s1==NULL) {
p->next=s1;s1=p;last=p;
}else{
last->next=p;p->next=NULL;last=p;
}
scanf("%d",&x);//read next
}
scanf("%d",&x);
while(x>=0) {
p=(ptr)malloc(sizeof(node));
p->data=x;
if(s2==NULL) {
p->next=s2;s2=p;last=p;
}else{
last->next=p;p->next=NULL;last=p;
}
scanf("%d",&x);
}
// p = s1;
// while (p!=NULL) {
// printf("%d",p->data);
// p=p->next;
// }
// p = s2;
// while (p!=NULL) {
// printf("%d",p->data);
// p=p->next;
// }
//
s3=(ptr)malloc(sizeof(node));
s3->next=NULL;
for(p=s1,q=s2,z=s3; p!=NULL&& q!=NULL; ) {
if(p->data==q->data) {
z->next=p;
z=z->next;
//printf("%d",p->data);
p=p->next;
q=q->next;
}elseif(p->datadata){
p=p->next;
}elseif(p->data>q->data){
q=q->next;
}
}
if((s3->next==NULL||s1==NULL)||s2==NULL) {
printf("NULL");
}else{
p = s3->next;
while(p!=NULL) {
printf("%d",p->data);
if(p->next!=NULL) {
printf(" ");
}
p=p->next;
}
}
// p = s1;
// while (p!=NULL) {
// printf("%d",p->data);
// p=p->next;
// }
}
