设有两个整数类型的顺序表A(有m个元素)和B(有n个元素),其元素均以从小到大的升序排列。试编写一个函数,将这两个顺序表合并成一个顺序表C,要求C的元素也以从小到大的升序排列。
时间: 2024-09-26 12:10:51 浏览: 8
要合并两个有序的整数顺序表 A 和 B 到一个新的有序列表 C,我们可以使用双指针的方法。这里提供一个 C++ 的简单示例:
```cpp
#include <iostream>
// 定义一个简单的整数顺序表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* A, ListNode* B) {
if (A == nullptr) return B; // 如果A为空,直接返回B
if (B == nullptr) return A; // 如果B为空,直接返回A
// 指针比较,选择较小的元素并移动相应的指针
if (A->val < B->val) {
A = A->next; // A的下一个元素
} else {
ListNode* temp = B; // 保存B链表中的当前节点,可能需要更新
B = B->next;
*temp = ListNode(A->val); // 将A的值放到B的位置
}
// 递归地合并剩余的部分
return mergeTwoLists(A, B);
}
// 创建一个新顺序表C,头部为合并后的结果
ListNode* createSortedList(ListNode* A, ListNode* B) {
ListNode* head = mergeTwoLists(A, B);
return head;
}
int main() {
// 假设你已经有了两个已排序的顺序表 A 和 B 的头结点
ListNode* listA = ...;
ListNode* listB = ...;
// 使用创建SortedList函数合并它们
ListNode* result = createSortedList(listA, listB);
// 打印合并后的顺序表C
while (result != nullptr) {
std::cout << result->val << " ";
result = result->next;
}
std::cout << "\n";
return 0;
}
```
在这个例子中,`mergeTwoLists` 函数负责合并两个链表,而 `createSortedList` 函数则用于创建新的有序链表 C。在 `main` 函数中,你需要先初始化 `listA` 和 `listB`,然后调用 `createSortedList` 来得到合并的结果。