PTA 两个有序链表序列的交集

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

输入格式:

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

输出格式:

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

输入样例:

1 2 5 -1 2 4 5 8 10 -1

输出样例：

2 5

程序代码：

#include <stdio.h> // 分别存放两链表数据 int a[2000000], b[2000000]; int main(){ int i = 0, j = 0; int x = 0, y = 0; while (scanf("%d", &a[x])){ if (a[x] == -1) break; x++; } while (scanf("%d", &b[y])){ if (b[y] == -1) break; y++; } // 做标记，等于0表示交集为空 int first = 0; while (i < x && j < y){ if (a[i] == b[j]){ if (!first){ printf("%d", a[i]); // 令标记等于1,表示不为空 first = 1; } else printf(" %d", a[i]); i++; j++; } else if (a[i] > b[j]) // 一链表数据大，二链表继续后移比较 j++; else // 二链表数据大，一链表继续后移比较 i++; } // 交集为空 if (!first) printf("NULL"); return 0; }