链表合并c++版本

解题思路:

1、定义 student 结构体用于存储学生信息，定义 linklist 结构体用于表示链表节点。

2、实现 mergetwolinklist 函数，接收两个链表头节点 heada 和 headb，将两个无序链表合并并返回一个有序链表头节点。

3、实现 getinput 函数用于从输入中获取学生信息并创建链表节点，然后返回该节点的指针。

4、在 main 函数中，先输入 numa 和 numb，表示两个链表的学生数量。

5、使用 getinput 函数依次输入学生信息，并按照学号升序插入到链表 lista 和 listb 中。

6、调用 mergetwolinklist 函数，将 lista 和 listb 两个链表合并成一个有序链表 list3。

7、遍历 list3 链表，输出合并后的有序学生信息

注意事项:注意释放动态分配的内存，避免内存泄漏。
参考代码:

#include <algorithm>

#include <cstdio>

#include <iostream>

using namespace std;

typedef struct {

    int id;

    int grade;

} student;

typedef struct linklist {

    student data;

    struct linklist* next;

} node;

node* mergetwolinklist(node* heada, node* headb) {

    node* dummy = new node;  // 头结点

    dummy->next = NULL;

    node* pa = heada, * pb = headb, * pc = dummy;

    while (pa && pb) {

        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) {

        pc->next = pa;

    } else {

        pc->next = pb;

    }

    node* res = dummy->next;

    delete (dummy);

    return res;

}

node* getinput() {

    int id;

    int grade;

    cin >> id >> grade;

    return new node{ {id, grade}, NULL };

}

int main() {

    node* lista = NULL;

    node* listb = NULL;

    int numa, numb;

    scanf("%d %d\n", &numa, &numb);

    student s;

    for (int i = 0; i < numa; i++) {

        cin >> s.id >> s.grade;

        node* newnode = new node{ s, NULL };  // 新结点

        if (!lista || s.id < lista->data.id) {  // 当前结点的学号是否小于头结点的学号

            newnode->next = lista;

            lista = newnode;

        } else {

            node* temp = lista;

            while (temp->next != NULL && 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, NULL };  // 新结点

        if (!listb || s.id < listb->data.id) {  // 当前结点的学号是否小于头结点的学号

            newnode->next = listb;

            listb = newnode;

        } else {

            node* temp = listb;

            while (temp->next != NULL && temp->next->data.id < s.id)  // 当前结点的下个结点的学号是否小于当前结点的学号

            {

                temp = temp->next;

            }

            newnode->next = temp->next;

            temp->next = newnode;

        }

    }

    node* list3 = NULL;

    list3 = mergetwolinklist(lista, listb);

    for (node* p = list3; p; p = p->next) {

        cout << p->data.id << " " << p->data.grade << endl;

    }

    // 释放 lista 链表节点的内存

    while (lista) {

        node* temp = lista;

        lista = lista->next;

        delete temp;

    }

    // 释放 listb 链表节点的内存

    while (listb) {

        node* temp = listb;

        listb = listb->next;

        delete temp;

    }

    // 释放 list3 链表节点的内存

    while (list3) {

        node* temp = list3;

        list3 = list3->next;

        delete temp;

    }

    return 0;

}