两个有序链表序列的合并

ゞ浴缸里的玫瑰 2022-05-09 04:33 176阅读 0赞

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

## 输入格式: ##

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

## 输出格式: ##

在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出`NULL`。

## 输入样例: ##

1 3 5 -1
    2 4 6 8 10 -1

## 输出样例: ##

1 2 3 4 5 6 8 10

#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)
            {
        
                pc->next=pa;
                pc=pa;
                pa=pa->next;
            }
            else if(pa->data>pb->data)
            {
        
                pc->next=pb;
                pc=pb;
                pb=pb->next;
            }
        }
        if(pa)
        {
        
            pc->next=pa;
        }
        else
        {
        
            pc->next=pb;
        }
        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;
    }