(标签-C++|关键词-头结点)

Question

C++编写代码，分别输入两个有序的整数序列(分别包含M和N个数据)，建立两个有序的单链表，将这两个有序单链表合并成为一个大的有序单链表。要求合并后的单链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。(去重)算法思想:
1.用pa遍历La的数据结点，pb遍历Lb的数据结点。
2.将La头结点用作新单链表Lc的头结点，让pc始终指向Lc的尾结点(初始时指向Lc)。
3.当pa和pb均不为空时循环:比较pa与pb之data域值，将较小者链到pc之后。
4.如此重复直到La或Lb为空，再将余下的链表链接到pc之后。编程要求
完成两个有序单链表的合并操作函数的定义，具体要求如下: void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc);
//归并有序单链表La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列

输入说明:
输入说明第一行输入有序表A的长度M;第二行依次输入有序表A的M个有序的整数;第三行输入有序表B的长度N;
第四行依次输入有序表B的N个有序的整数。输出说明:
输出合并后的有序单链表所包含的M+N个有序的整数。
输入样例1:
5
10 15 20 25 30
6
12 22 32 42 52 62
输出样例1:
10 12 15 20 22 25 30 32 42 52 62

Answer 1

【以下回答由 GPT 生成】

#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 InsertList(LinkList &L, int x) {
    LNode *p = L;
    while (p->next != NULL && p->next->data < x) {
        p = p->next;
    }
    LNode *newNode = new LNode;
    newNode->data = x;
    newNode->next = p->next;
    p->next = newNode;
}

// 合并两个有序单链表
void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc) {
    LNode *pa = La->next;
    LNode *pb = Lb->next;
    Lc = La; // 将La的头结点作为Lc的头结点
    LNode *pc = Lc; // pc指向Lc的尾结点

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

    pc->next = (pa != NULL) ? pa : pb; // 将剩余的链表链接到pc之后
    delete Lb; // 释放Lb的头结点
}

int main() {
    LinkList La, Lb, Lc;
    int m, n, num;

    // 初始化La
    cin >> m;
    InitList(La);
    for (int i = 0; i < m; i++) {
        cin >> num;
        InsertList(La, num);
    }

    // 初始化Lb
    cin >> n;
    InitList(Lb);
    for (int i = 0; i < n; i++) {
        cin >> num;
        InsertList(Lb, num);
    }

    // 合并La和Lb得到Lc
    MergeList(La, Lb, Lc);

    // 输出合并后的有序单链表
    LNode *p = Lc->next;
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;

    return 0;
}

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^