已知两个非降序链表序列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<stdlib.h>
using namespace std;
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;
void sort(LNode * &L)
{
	LNode *p,*pre,*q;
	p=L->next->next;
	L->next->next = NULL;
	while(p!=NULL)
	{
		q=p->next;
		pre = L;
		while(pre->next!=NULL&&pre->next->data<p->data){
			pre=pre->next;
		}
		p->next=pre->next;
		pre->next = p;
		p=q;
	}
}
int main()
{
	LinkList s ,L;
	s =(LinkList)malloc(sizeof(LNode));
	L =(LinkList)malloc(sizeof(LNode));
	L=s;
	s->next=NULL;
	int a=0;
	cin>>a;
	//s=s->next;
	//s->data=0;
	while(a!=-1)
	{
		LinkList k =(LinkList)malloc(sizeof(LNode));
		k->data=a;
		k->next=NULL;
		k->next = s->next;
		s->next=k;
		cin>>a;
		
	}
	cin>>a;
	while(a!=-1)
	{
		LinkList k =(LinkList)malloc(sizeof(LNode));
		k->data=a;
		k->next=NULL;
		k->next = s->next;
		s->next=k;
		cin>>a;
		
	}
	if(L->next==NULL){
		cout<<"NULL";
	}else{
		sort(L);
		L=L->next;
		while(L->next)
		{
			cout<<L->data<<" ";
			L=L->next;
		} 
		cout<<L->data;
	}
	return 0;
}