浙江大学PAT上机题解析之2-11. 两个有序链表序列的合并

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

输入格式说明：

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

输出格式说明：

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

样例输入与输出：

序号	输入	输出
1	1 3 5 -1 2 4 6 8 10 -1	1 2 3 4 5 6 8 10
2	1 2 3 4 5 -1 1 2 3 4 5 -1	1 1 2 2 3 3 4 4 5 5
3	-1 -1	NULL

 //注意：当我用cin,cout的时候，最后一个case超时，换做scanf,printf之后就AC了，足以证明如果对运行效率要求较高的话还是要选择stdio的输入输出

#include <cstdio>
#include <list>

using namespace std;


int main()
{
	list<int>  list1;
	list<int>  list2;
	list<int>::iterator it,it1,it2;

	int val=0;
	bool flag = false;
	while(scanf("%d",&val),val!=-1)
		list1.push_back(val);
	while(scanf("%d",&val),val!=-1)		
		list2.push_back(val);

	if (list1.empty()&&list2.empty())
		/*cout<<"NULL"<<endl;*/
		printf("NULL
");

	for (it1=list1.begin(),it2=list2.begin();it1!=list1.end()&&it2!=list2.end();)
	{

		if (*it1 < *it2)
		{
			if (flag)
				/*cout<<" ";*/
				printf(" ");
			else
				flag = true;
			/*cout<<*it1;*/
			printf("%d",*it1);
			it1++;
		}
		else
		{
			if (flag)
			printf(" ");
			else
				flag = true;
		/*	cout<<*it2;*/
				printf("%d",*it2);
			it2++;
		}
	}
	if (it1==list1.end())
	{
		while(it2!=list2.end()) {/*cout<<" "<<*it2++;*/	printf(" %d",*it2);it2++;}
	}
	if (it2==list2.end())
	{
		while(it1!=list1.end())  {/*cout<<" "<<*it1++;*/printf(" %d",*it1);it1++;}
	}
	/*cout<<endl;*/
	printf("
");


	//system("pause");
	return 0;
}