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

zhuaizhai 下午好🌅🌅🌅
本答案参考ChatGPT-3.5

解决方案：

首先，我们需要定义一个单链表的结构体，其中包含数据域和指向下一个结点的指针。可以使用如下的结构体定义：

struct ListNode {
    int data;
    ListNode* next;
};

根据输入样例，我们需要实现一个合并函数MergeList，该函数接受三个单链表参数作为输入，将La和Lb两个有序单链表合并成一个新的有序单链表Lc。

下面是实现MergeList函数的步骤：

1. 首先，创建一个头结点head并将其指针指向La的头结点。
2. 创建一个指针pa并将其指向La的头结点。创建一个指针pb并将其指向Lb的头结点。
3. 创建一个指针pc并将其指向头结点。这个指针pc将用于链接新的有序单链表Lc中的结点。
4. 使用循环遍历La和Lb，比较pa和pb的data域值，将较小者的结点链接到pc的后面。
5. 如果pa或pb为空，则将剩余的链表链接到pc的后面。
6. 返回合并后的有序单链表Lc。

下面是具体实现的代码：

void MergeList(ListNode* La, ListNode* Lb, ListNode* Lc) {
    ListNode* pa = La->next;
    ListNode* pb = Lb->next;
    ListNode* 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;

    // 释放多余的结点空间
    La->next = NULL;
    Lb->next = NULL;
}

在主函数中，我们可以按照输入要求输入La和Lb的数据，并调用MergeList函数来合并两个有序单链表，最后遍历输出合并后的有序单链表Lc的数据。

下面是完整的代码：

#include <iostream>
using namespace std;

struct ListNode {
    int data;
    ListNode* next;
};

void MergeList(ListNode* La, ListNode* Lb, ListNode* Lc) {
    ListNode* pa = La->next;
    ListNode* pb = Lb->next;
    ListNode* 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;

    La->next = NULL;
    Lb->next = NULL;
}

int main() {
    int M, N;
    cin >> M;
    ListNode* LaHead = new ListNode;
    ListNode* La = LaHead;
    for (int i = 0; i < M; ++i) {
        int num;
        cin >> num;
        ListNode* newNode = new ListNode;
        newNode->data = num;
        La->next = newNode;
        La = newNode;
    }
    cin >> N;
    ListNode* LbHead = new ListNode;
    ListNode* Lb = LbHead;
    for (int i = 0; i < N; ++i) {
        int num;
        cin >> num;
        ListNode* newNode = new ListNode;
        newNode->data = num;
        Lb->next = newNode;
        Lb = newNode;
    }

    ListNode* LcHead = new ListNode;
    MergeList(LaHead, LbHead, LcHead);

    ListNode* Lc = LcHead->next;
    while (Lc != NULL) {
        cout << Lc->data << " ";
        Lc = Lc->next;
    }

    // 释放内存
    ListNode* p = LcHead;
    while (p != NULL) {
        ListNode* temp = p->next;
        delete p;
        p = temp;
    }

    return 0;
}

以上是完整的解决方案和代码。输入La和Lb的数据后，程序将合并两个有序单链表，并输出合并后的有序单链表Lc的数据。