有序链表的异地合并

前言：

现在是凌晨，今天下午ACM就考核了，我要临时抱一下佛退，赶紧复习一下归并排序，但在题库里面找来找去，没找到非常合适的，只找到这个题，就当作练练手吧。

题目描述：

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



结尾无空行

思路：

由于是异地合并，所有我们需要三个指针a.b.c，一个指向A当前所比较的数，一个指向B当前所比较的数，还要一个指向C现在的尾部，这样我们就是通过尾插法对C进行添加数据了。每次我们只需要比较a和b中哪个小，然后将其数据复制到一个新的节点上，再将这个节点插到c的后面就行了，而a或b中较小的也要向后移一下。当其中一链表比完了后，只需要把另一个链表全接上去就行了，就这么简单。

源码：

#include<iostream>
using namespace std;
typedef struct Lnode{
    int data;
    Lnode* next;
}Lnode,*Linklist;
//尾插法创建链表
void Create(Linklist &l){
    l=new Lnode;
    l->next=NULL;
    Lnode* r=l;
    int d;
    cin>>d;
    while(d!=-1){
        Lnode* p=new Lnode;
        p->data=d;
        p->next=r->next;
        r->next=p;
        r=p;
        cin>>d;
    }
}
//合并函数
void merge(Linklist &a,Linklist &b,Linklist &c){
    c=new Lnode;
    c->next=NULL;
    Lnode* r=c;
    Lnode* m=a->next;
    Lnode* n=b->next;
    while(m&&n){
        if(m->data>=n->data){
            Lnode* p=new Lnode;
            p->data=n->data;
            p->next=r->next;
            r->next=p;
            r=p;
            n=n->next;
        }else{
            Lnode* p=new Lnode;
            p->data=m->data;
            p->next=r->next;
            r->next=p;
            r=p;
            m=m->next;
        }
    }
    while(m){
        Lnode* p=new Lnode;
        p->data=m->data;
        p->next=r->next;
        r->next=p;
        r=p;
        m=m->next;
    }
    while(n){
        Lnode* p=new Lnode;
        p->data=n->data;
        p->next=r->next;
        r->next=p;
        r=p;
        n=n->next;
    }
}
int main(){
    Linklist a,b,c;
    Create(a);
    Create(b);
    merge(a,b,c);
    if(!c->next){
        cout<<"NULL";
    }else{
        Lnode* p=c->next;
        while(p){
            if(p->next){
                cout<<p->data<<' ';
                p=p->next;
            }else{
                cout<<p->data;
                p=p->next;
            }
            
        }
    }
    return 0;
}