浙江大学PAT上机题解析之2-12. 两个有序链表序列的交集

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

输入格式说明：

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

输出格式说明：

在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出“NULL”。

样例输入与输出：

1 2 5 -12 4 5 8 10 -1

2 5

1 3 5 -12 4 6 8 10 -1

NULL

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

1 2 3 4 5

3 5 7 -12 3 4 5 6 7 8 -1

3 5 7

-110 100 1000 -1

NULL

#include <cstdio>#include <list>#include <iostream>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);int t = 0;for (it1=list1.begin(),it2=list2.begin();it1!=list1.end()&&it2!=list2.end();){if (*it1 < *it2){it1++;}else if (*it1 > *it2){it2++;}else{if (flag)printf(" ");elseflag = true;printf("%d",*it1);it2++;it1++;t = 1;}}    if (list1.empty()||list2.empty()||t==0)    {printf("NULL");    }    printf("\n");//system("pause");return 0;}

//这道题确实花了我不少心思与时间，之前也是最后一个CASE总是出错，一直不知道为什么，晚上回到寝室之后与同学交流了一下(得一志同道合良友真的很重要)，才找到原因，之前我一直在输入的时候把重复项删除了，但是 事实是 2 2 与2 2的交集是2 2 而不是2，果真理清题意实在是很重要。