两个有序链表序列的交集-蒲公英云

两个有序链表序列的交集

- 日理万妓 2022-05-09 04:58 244阅读 0赞

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

输入格式:

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

输出格式:

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

输入样例:

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

输出样例:

2 5
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW   -2
typedef int  Status;
typedef int  ElemType; 
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LNode,*LinkList; 
Status ListCreate_CL(LinkList &CL);
void ListPrint_CL(LinkList &L)
{
    LNode * t = L->next;
    int firstNum = 1;
    if(t == NULL) printf("NULL\n");
    while(t != NULL)
    {
        if(firstNum)
        {
            printf("%d", t->data);
            firstNum = 0;
        }
        else
            printf(" %d", t->data);
        t = t->next;
    }
}
int main()
{
    LinkList c1,c2,c3,pa,pb,pc;
    c3=(LinkList)malloc(sizeof(LNode));
    c3->next=NULL;
    ListCreate_CL(c1);
    ListCreate_CL(c2);
    pa=c1->next;
    pb=c2->next;
    pc=c3;
    while(pa&&pb)
    {
        if(pa->data<pb->data)pa=pa->next;
        else if(pa->data>pb->data)pb=pb->next;
        else
        {
            pc->next=pa;
            pa=pa->next;
            pb=pb->next;
            pc=pc->next;
        }
    }
    pc->next=NULL;
    ListPrint_CL(c3);
    return 0;
}
Status ListCreate_CL(LinkList &CL)
{
    CL = (LinkList)malloc(sizeof (LNode) );
    int n,f=1;
    LNode *p,*q;
    CL->next=NULL;
    p=CL;
    while(f)
    {
        scanf("%d",&n);
        if(n>=0)
        {
            q=(LNode *)malloc(sizeof(LNode));
            q->data=n;
            p->next=q;
            p=q;
        }
        else
        {
            f=0;
            p->next=NULL;
        }
    }
    return OK;
}