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

已知两个非降序链表序列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;
}

 

上一篇:为什么0.1 + 0.2 != 0.3 ???


下一篇:学习笔记-元数据节点号 20210302