7-5 两个有序链表序列的交集 (20分) 已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。 输入格式: 输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−

时间：2025-05-16 08:08:46

7-5 两个有序链表序列的交集 (20分)

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。

输入格式:

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式:

在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

1 2 5 -1
2 4 5 8 10 -1

输出样例:

2 5
#include ""
#include ""
#define N 100000
typedef struct linknode
{
    int data;
    struct linknode *next;
    
}node,*ptr;

int main(){
    ptr s1,s2,s3,p,q,z,last;
    int x;
    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;
        }else if (p->data<q->data){
            p=p->next;
        }else if (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;
//    }

    
    
}

 

相关文章