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

2-3 两个有序链表序列的合并

分数 4

作者 DS课程组

单位 浙江大学

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

输入格式:

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

输出格式:

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

输入样例:

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

输出样例:

1 2 3 4 5 6 8 10

依旧是第n遍写这个题（又敲了一遍）

答案

#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) {
    LNode *newNode = new LNode;
    newNode->data = num;
    newNode->next = NULL;
    tail->next = newNode;
    tail = newNode;
}

// 合并L1和L2
LinkList Merge(LinkList L, LinkList L1, LinkList L2) {
    LinkList p = L1->next; // 用于遍历L1
    LinkList q = L2->next; // 用于遍历L2
    LinkList tail = L;
    while (p != NULL && q != NULL) { // 有一个先遍历完就退出循环
        if (p->data <= q->data) { // p当前的小
            insertAtTail(tail, p->data);
            p = p->next; // p往后挪
        } else { // q当前的小
            insertAtTail(tail, q->data);
            q = q->next; // q往后挪
        }
    }
    // L1遍历完了，将L2剩余的放到新表
    while (q != NULL) {
        insertAtTail(tail, q->data);
        q = q->next;
    }// L2遍历完了，将L1剩余的放到新表
    while (p != NULL) {
        insertAtTail(tail, p->data);
        p = p->next;
    }
    return L;
}

// 打印链表
void printList(LinkList L) {
    bool isFirst = true;
    LinkList p = L->next;
    if (p == NULL) { // 若新链表为空，输出NULL
        cout << "NULL";
        return;
    }
    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 < 0) {
            break;
        }
        insertAtTail(tail1, num);
    }

    // 输入第二个链表
    LinkList tail2 = L2;
    while (cin >> num) {
        if (num < 0) {
            break;
        }
        insertAtTail(tail2, num);
    }

    // 合并两个链表到一个新表
    LinkList L;
    initList(L);
    L = Merge(L, L1, L2);
    printList(L);
}

一遍过！耶耶耶