【HBU】7-3 两个有序链表序列的交集 (20分)-蒲公英云

【HBU】7-3 两个有序链表序列的交集 (20分)

清疚 2022-12-22 04:54 262阅读 0赞

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

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

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

输入样例:

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

输出样例:

2 5

将两个链表分别放进两个队列里，比较队首元素大小，如果相等则输出，再出队；如果不相等，将较大的那个元素出队，知道有一个队列为空结束

#include <iostream>
#include <queue>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    queue<int> a, b;
    int t;
    while(1){
        cin >> t;
        if(t == -1) break;
        a.push(t); 
    }
    while(1){
        cin >> t;
        if(t == -1) break;
        b.push(t); 
    }
    int num = 0;
    while(!a.empty() && !b.empty()){
        if(a.front() < b.front()) a.pop();
        else if(a.front() > b.front()) b.pop();
        else {
            if(num) cout << " ";
            cout << a.front();
            a.pop();
            b.pop();
            num++;
        }
    }
    if(num == 0) cout << "NULL";
}