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 306
12 22 32 42 52 62
输出样例1:
10 12 15 20 22 25 30 32 42 52 62

Answer 1

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

下面是解决该问题的具体步骤：

1. 首先，需要定义一个链表节点的结构体。每个节点包含一个整数data和指向下一个节点的指针next。

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

1. 接着，需要定义两个有序链表的头指针La和Lb，并初始化为空指针。

ListNode* La = nullptr;
ListNode* Lb = nullptr;

1. 然后，根据输入的有序整数序列构建两个有序链表La和Lb。

void CreateList(ListNode*& head, int len) {
    for (int i = 0; i < len; i++) {
        int num;
        cin >> num;
        ListNode* newNode = new ListNode();
        newNode->data = num;
        newNode->next = nullptr;
        
        if (head == nullptr) {
            head = newNode;
        } else {
            ListNode* p = head;
            while (p->next != nullptr) {
                p = p->next;
            }
            p->next = newNode;
        }
    }
}

int M, N;
cin >> M;
CreateList(La, M);
cin >> N;
CreateList(Lb, N);

1. 定义一个新的链表Lc，并用La的头结点作为Lc的头结点。

ListNode* Lc = La;

1. 遍历La和Lb，将较小者的节点插入到Lc的尾部

ListNode* pa = La;
ListNode* pb = Lb;
ListNode* pc = Lc;

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

// 将剩余的节点链接到Lc的尾部
if (pa != nullptr) {
    pc->next = pa;
} else if (pb != nullptr) {
    pc->next = pb;
}

1. 最后，遍历输出合并后的有序链表Lc中的所有元素。

pc = Lc;
while (pc != nullptr) {
    cout << pc->data << " ";
    pc = pc->next;
}

完整的代码如下：

#include <iostream>
using namespace std;

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

void CreateList(ListNode*& head, int len) {
    for (int i = 0; i < len; i++) {
        int num;
        cin >> num;
        ListNode* newNode = new ListNode();
        newNode->data = num;
        newNode->next = nullptr;
        
        if (head == nullptr) {
            head = newNode;
        } else {
            ListNode* p = head;
            while (p->next != nullptr) {
                p = p->next;
            }
            p->next = newNode;
        }
    }
}

void MergeList(ListNode* La, ListNode* Lb, ListNode*& Lc) {
    Lc = La;
    ListNode* pa = La;
    ListNode* pb = Lb;
    ListNode* pc = Lc;

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

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

int main() {
    int M, N;
    cin >> M;
    ListNode* La = nullptr;
    CreateList(La, M);

    cin >> N;
    ListNode* Lb = nullptr;
    CreateList(Lb, N);

    ListNode* Lc = nullptr;
    MergeList(La, Lb, Lc);

    ListNode* pc = Lc;
    while (pc != nullptr) {
        cout << pc->data << " ";
        pc = pc->next;
    }
    cout << endl;

    return 0;
}

希望对你有所帮助！