7-1 两个有序链表序列的合并 (15 分)

84 阅读 0 评论 56 点赞

我是靠谱客的博主年轻苗条，最近开发中收集的这篇文章主要介绍7-1 两个有序链表序列的合并 (15 分)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

7-1 两个有序链表序列的合并 (15 分)

**
已知两个非降序链表序列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 <stdlib.h>
#define INCRESIZE 100

typedef struct node{
    int data;
    struct node *next;
}lnode,*linklist;

void initlist(linklist *l){//头指针
    *l=(linklist)malloc(sizeof(lnode));
    (*l)->next=NULL;
}

int initlist1(linklist *l){//头指针
    *l=(linklist)malloc(sizeof(lnode));
    if(!*l)
        return 0;
    (*l)->next=NULL;
    return 1;
}

void inputlist2(linklist l){//尾接法
    int x;
    linklist p,r;
    r=l;
    scanf("%d",&x);
    while(x!=-1){
        p=(linklist)malloc(sizeof(lnode));
        p->data=x;
        r->next=p;
        r=p;
        scanf("%d",&x);
    }
    r->next=NULL;
}

linklist unionlist(linklist la,linklist lb){//链表合并
    
    linklist pa,pb,pc,q;
    pc=(linklist)malloc(sizeof(lnode));
    pa=la->next;
    pb=lb->next;
    pc->next=NULL;
    q=pc;
    
    while(pa!=NULL&&pb!=NULL){
        if(pa->data<=pb->data){
            q->next=pa;
            pa=pa->next;
            q=q->next;
        }
        else{
            q->next=pb;
            pb=pb->next;
            q=q->next;
        }
        
    }
    if(pa!=NULL)
        q->next=pa;
    if(pb!=NULL)
        q->next=pb;
    return pc;
}

void outputlist(linklist l){//输出
    linklist p;
    p=l->next;
    if(p==NULL){
        printf("NULL");
    }
    else{
        while(p)
        {
            printf("%d",p->data);
            if(p->next)
                printf(" ");
            p=p->next;
        }
    }
}

int main(int argc, const char * argv[]) {
    
    linklist l1,l2,l3;
    initlist(&l1);
    initlist(&l2);
    initlist(&l3);
    
    inputlist2(l1);
    inputlist2(l2);
    
    l3=unionlist(l1,l2);
    outputlist(l3);
    
    return 0;
}