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

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

输入格式说明：

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

输出格式说明：

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

样例输入与输出：

1 3 5 -12 4 6 8 10 -1

1 2 3 4 5 6 8 10

1 2 3 4 5 -11 2 3 4 5 -1

1 1 2 2 3 3 4 4 5 5

-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\n");for (it1=list1.begin(),it2=list2.begin();it1!=list1.end()&&it2!=list2.end();){if (*it1 < *it2){if (flag)/*cout<<" ";*/printf(" ");elseflag = true;/*cout<<*it1;*/printf("%d",*it1);it1++;}else{if (flag)printf(" ");elseflag = 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("\n");//system("pause");return 0;}