PTA（链表）2-6 两个有序链表合并（新表不含重复元素）

2-6 两个有序链表合并（新表不含重复元素）

分数 4

作者 陈晓梅

单位 广东外语外贸大学

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。
要求S3中没有重复元素。

输入格式:

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

输出格式:

在一行中输出合并后新的非降序链表，要求链表中没有重复元素。数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

在这里给出一组输入。例如：

1 3 3 5 8 -1
2 3 4 6 8 10 -1

输出样例:

在这里给出相应的输出。例如：

1 2 3 4 5 6 8 10

• 又写了一题归并，但这次是不能有重复元素，之前链表的归并有

  • PTA（链表）1-6 两个有序链表序列的合并（C） | zhangzhang-blog

  • PTA（链表）2-3 两个有序链表序列的合并（C++） | zhangzhang-blog

• 不能有重复元素：我使用的是高效的查找表——布尔数组

我的正确答案

#include<iostream>
using namespace std;

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

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

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

// 合并两个链表到新的链表L
void merge(LinkList &L, LinkList &L1, LinkList &L2) {
    int Max_size = 10000;
    bool exists[Max_size]; // 定义布尔数组，用于标记是否插入过
    // 初始化
    for (int i = 0; i < Max_size; ++i) {
        exists[i] = false;
    }

    LinkList p = L1->next; // 遍历L1
    LinkList q = L2->next; // 遍历L2
    LinkList tail = L; // 便于尾插法插入L
    while (p != NULL && q != NULL) {
        if (p->data <= q->data) {
            if (!exists[p->data]) {
                insertAtTail(tail, p->data);
            }
            exists[p->data] = true;
            p = p->next;
        } else {
            if (!exists[q->data]) {
                insertAtTail(tail, q->data);
            }
            exists[q->data] = true;
            q = q->next;
        }
    }
    // 当L1遍历完，把L2剩余的符合要求的元素插入
    while (q != NULL) {
        if (!exists[q->data]) {
            insertAtTail(tail, q->data);
        }
        exists[q->data] = true;
        q = q->next;
    }
    // 当L2遍历完，把L1剩余的符合要求的元素插入
    while (p!= NULL) {
        if (!exists[p->data]) {
            insertAtTail(tail, p->data);
        }
        exists[p->data] = true;
        p = p->next;
    }
}

// 打印链表
void printList(LinkList L) {
    bool isFirst = true;
    LinkList p = L->next;
    if (L->next == NULL) {
        cout << "NULL";
    }
    while (p != NULL) {
        if (!isFirst) {
            cout << " ";
        }
        isFirst = false;
        cout << p->data;
        p = p->next;
    }
}

int main() {
    LinkList L1;
    LinkList L2;
    initList(L1);
    initList(L2);

    int num;
    // 尾插法读取第一个链表
    LinkList tail1 = L1; // 定义尾指针便于插入
    while (cin >> num) {
        if (num == -1) {
            break;
        }
        insertAtTail(tail1, num);
    }
    // 尾插法读取第二个链表
    LinkList tail2 = L2; // 定义尾指针便于插入
    while (cin >> num) {
        if (num == -1) {
            break;
        }
        insertAtTail(tail2, num);
    }
    LinkList L;
    initList(L);
    merge(L, L1, L2);
    printList(L);
}