1509: 两个有序链表序列的合并
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 293 Solved: 169
[Submit][Status][Web Board]
Description
已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的并集新非降序链表S3。
Input
输入分2行，分别在每行给出由若干个正整数构成的非降序序列，用-1表示序列的结尾（-1不属于这个序列）。数字用空格间隔。序列中元素的个数不超过100
Output
在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格。
Sample Input
1 3 5 -1
2 4 6 8 10 -1
Sample Output
1 2 3 4 5 6 8 10
【分析】
- 尝试了下用STL里的list容器，定义迭代器，真的方便了很多呀~
- list：双向链表，任意位置插入、删除；在两端增删元素具有较佳的性能，不支持随机存取；
#include<bits/stdc++.h>
using namespace std;
list<int> list1,list2;//双向链表（STL顺序容器）
list<int>::iterator it,it1,it2;//迭代指针
int main()
{int x;bool flag=false;//输出格式空格需要while(~scanf("%d",&x)&&x!=-1)list1.push_back(x);while(~scanf("%d",&x)&&x!=-1)list2.push_back(x);for(it1=list1.begin(),it2=list2.begin();it1!=list1.end(),it2!=list2.end();)//注意分号不要漏掉{if(*it1 < *it2){if(flag)cout<<" ";else flag=true;cout<<*it1;it1++;}else{if(flag)cout<<" ";else flag=true;cout<<*it2;it2++;}}if(it1==list1.end())while(it2!=list2.end()){ cout<<" "<<*it2; it2++; }if(it2==list2.end())while(it1!=list1.end()){ cout<<" "<<*it1; it1++; } cout<<endl; return 0;
}