PTA（顺序表）2-4 两个有序链表序列的交集

zhangzhang2025-10-202025-10-20

2-4 两个有序链表序列的交集

分数 6

作者 DS课程组

单位浙江大学

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

输入格式:

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

输出格式:

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

输入样例:

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

输出样例:

2 5

此题我是按照PTA（顺序表）2-5 集合减法 | zhangzhang-blog做的，用的布尔数组瞬间判断元素 num 是否在序列中，咋就是有个答案不对

我的部分正确

#include <iostream>
using namespace std;

// 定义链表结构
typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

const int Max_ELEM = 30000;

// 标记数组
bool exists[Max_ELEM+1];

// 初始化链表
void initList(LinkList &L) {
    L = new LNode;
    L->next = NULL;
}

// 尾插法插入链表
void insertAtTail(LinkList &tail, int num) {
    LNode *newNode = new LNode;
    newNode->data = num;
    newNode->next = NULL;
    tail->next = newNode;
    tail = newNode; // 更新尾指针
}

int main() {
    int num;

    // 初始化标记数组
    for (int i = 0; i <= Max_ELEM; ++i) {
        exists[i] = false;
    }
    // 将第一个序列放入到标记数组
    while (cin >> num) {
        if (num < 0) {
            break;
        }
        if (num >= 0 && num <= Max_ELEM) {
            exists[num] = true;
        }
    }

    LinkList L;
    initList(L);
    // 读取第二个序列，将也在序列一中的尾插进入链表
    LinkList tail = L; // 定义一个尾指针便于插入
    while (cin >> num) {
        if (num < 0) {
            break;
        }
        if (num >= 0 && num <= Max_ELEM) {
            if (exists[num]) {
                insertAtTail(tail, num);
                exists[num] = false; // 确保了S2中即使有重复的num,也不会再次被插入到L中。
            }
        }
    }

    // 打印交集
    bool hasTheSame = false; // 用于检查是否有相同元素
    bool isFirst = true;
    LinkList p = L->next; // 用于遍历链表
    while (p != NULL) {
        if (!isFirst) {
            cout << " ";
        }
        cout << p->data;
        isFirst = false;
        hasTheSame = true;
        p = p->next;
    }
    if (!hasTheSame) {
        cout << "NULL";
    }
}

测试点	内存(KB)	用时(ms)	结果	得分
0	552	2	答案正确	1 / 1
1	560	2	答案正确	1 / 1
2	572	2	答案正确	1 / 1
3	576	2	答案正确	1 / 1
4	572	2	答案正确	1 / 1
5	644	249	答案错误	0 / 1