20-4-21--链表--两个有序链表序列的合并

已知两个非降序链表序列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 <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct node {
    int date;
    struct node* next;
}linklist;
typedef struct node* plink;
plink addnode(int a,plink end)
{
    plink t=new linklist;
    end->next =t;
    t->date =a;
    t->next =NULL;
    return t;
}
plink deletelist(plink head)
{
    plink t=head->next ;
    plink p;
    while(t)
    {
        p=t;
        t=t->next ;
        delete(p);
        
    }
}
vector <int> v;
int main(){
    plink h1=new linklist,h2=new linklist,end;
    h1->next =NULL;
    h2->next =NULL;
    end=h1;
    int t;
    cin>>t;
    while(t!=-1)
    {
        end=addnode(t,end);
        cin>>t;
    }
    end=h2;
    cin>>t;
    while(t!=-1)
    {
        end=addnode(t,end);
        cin>>t;
    }
    if(h1->next ==NULL&&h2->next ==NULL)
    {
        cout<<"NULL"<<endl;
    }else{
        plink node1=h1->next ,node2=h2->next ;
        while(node1)
        {
            v.push_back(node1->date );
            node1=node1->next ;
        }
        while(node2)
        {
            v.push_back(node2->date );
            node2=node2->next ;
        }
        sort(v.begin(),v.end() );
        for(int i=0;i<v.size();i++)
        {
            cout<<v[i];
            if(i!=v.size()-1)
            {
                cout<<' ';
            }
        }
        
    }
    
    deletelist(h1);
    deletelist(h2);
    delete(h1);
    delete(h2);
    
    
}

结果如下：