题目 1052: [编程入门]链表合并

已有a、b两个链表，每个链表中的结点包括学号、成绩。要求把两个链表合并，按学号升序排列。

输入格式

第一行，a、b两个链表元素的数量N、M,用空格隔开。 接下来N行是a的数据 然后M行是b的数据 每行数据由学号和成绩两部分组成

输出格式

按照学号升序排列的数据

样例输入

2 3
5 100
6 89
3 82
4 95
2 10

样例输出

2 10
3 82
4 95
5 100
6 89

学号的升序怎么写的：

1. 当插入一个新的节点时，需要按照学号的升序将节点插入到链表中。

2. 对于链表A和链表B，一开始它们可能是无序的。但在将它们合并成一个新的链表时，需要保持新链表中的节点按照学号的升序排列。

3. 针对插入操作，可以使用两种方法：

   • 每次插入时，遍历链表找到合适的插入位置。比较新节点的学号与当前节点的学号大小，找到合适的位置后，将新节点插入到该位置。这种方法的时间复杂度为O(N)，其中N是链表的长度。

   • 使用递归或迭代的方法，在插入新节点时保持链表的有序性。比较新节点的学号与当前节点的学号大小，根据大小关系选择插入到当前位置或继续递归或迭代到下一个节点。这种方法的时间复杂度也为O(N)。

思路：

1. mergeLinkedList函数实现了两个有序链表的合并操作。它接收两个链表的头节点指针heada和headb，然后创建一个虚拟头节点dummy作为合并后的链表头部的前一个节点。同时定义三个指针pa、pb和pc分别指向链表A、B和合并后的链表的当前节点。通过比较两个链表节点的学号，每次选择较小的学号节点连接到合并后的链表中，直到其中一个链表遍历完。最后将剩余的链表直接连接到合并后的链表的末尾。最后返回合并后的链表的头节点指针。

2. getInput函数从标准输入中获取一个学生信息，并创建一个新的节点来存储这个学生信息。返回这个新节点的指针。

3. 在main函数中，首先初始化两个链表的头节点指针lista和listb为nullptr。然后从标准输入中读取两个整数numa和numb分别表示链表A和链表B的长度。接下来，使用一个循环读取numa个学生信息，并按照“学号的升序”将学生插入链表A中。再使用一个循环读取numb个学生信息，并按照学号的升序将学生插入链表B中。

4. 调用mergeLinkedList函数将链表A和链表B合并成一个新的链表，并将返回的合并链表的头节点指针保存在mergedList中。

5. 使用一个循环打印合并后的链表的每个节点的学号和成绩。

6. 最后，使用一个循环释放合并后的链表中每个节点的内存，避免内存泄漏。

#include <iostream>

using namespace std;

struct student {
    int id;
    int grade;
};

struct Node {
    student data;
    Node* next;
};

Node* mergeLinkedList(Node* heada, Node* headb) {
    Node* dummy = new Node;  // 创建一个虚拟头节点
    dummy->next = nullptr;

    Node* pa = heada;
    Node* pb = headb;
    Node* pc = dummy;

    while (pa != nullptr && pb != nullptr) {
        if (pa->data.id < pb->data.id) {
            pc->next = pa;
            pa = pa->next;
        }
        else {
            pc->next = pb;
            pb = pb->next;
        }
        pc = pc->next;
    }

    if (pa != nullptr) {
        pc->next = pa;
    }
    else {
        pc->next = pb;
    }

    Node* result = dummy->next;
    delete dummy;
    return result;
}

Node* getInput() {
    int id, grade;
    cin >> id >> grade;
    Node* newNode = new Node{ {id, grade}, nullptr };
    return newNode;
}

int main() {
    Node* lista = nullptr;
    Node* listb = nullptr;
    int numa, numb;
    cin >> numa >> numb;

    student s;
    for (int i = 0; i < numa; i++) {
        cin >> s.id >> s.grade;
        Node* newNode = new Node{ s, nullptr };

        if (!lista || s.id < lista->data.id) {
            newNode->next = lista;
            lista = newNode;
        }
        else {
            Node* temp = lista;
            while (temp->next != nullptr && temp->next->data.id < s.id) {
                temp = temp->next;
            }
            newNode->next = temp->next;
            temp->next = newNode;
        }
    }

    for (int i = 0; i < numb; i++) {
        cin >> s.id >> s.grade;
        Node* newNode = new Node{ s, nullptr };

        if (!listb || s.id < listb->data.id) {
            newNode->next = listb;
            listb = newNode;
        }
        else {
            Node* temp = listb;
            while (temp->next != nullptr && temp->next->data.id < s.id) {
                temp = temp->next;
            }
            newNode->next = temp->next;
            temp->next = newNode;
        }
    }

    Node* mergedList = mergeLinkedList(lista, listb);

    // 打印合并后的链表
    Node* temp = mergedList;
    while (temp != nullptr) {
        cout << temp->data.id << " " << temp->data.grade << endl;
        temp = temp->next;
    }

    // 释放内存
    while (mergedList != nullptr) {
        Node* temp = mergedList;
        mergedList = mergedList->next;
        delete temp;
    }

    return 0;
}