有顺序表A和B,其元素均按从小到大的升序排列,编写一个算法,将它们合并成一个顺序表C,要求C的元素也按从小到大的升序排列。c++代码
时间: 2024-09-20 15:01:39 浏览: 18
你可以使用C++中的双指针法来合并两个有序列表A和B。这里是一个简单的示例:
```cpp
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* A, ListNode* B) {
// 如果A或B为空,则直接返回另一个非空链表
if (A == nullptr) return B;
if (B == nullptr) return A;
// 使用指针比较当前节点值并选择较小的一个添加到结果链表中
ListNode* result = (A->val <= B->val) ? A : B;
A = (A->val <= B->val) ? A->next : A;
B = (A->val <= B->val) ? B->next : B;
// 将剩余的节点逐个添加到结果链表中
while (A != nullptr && B != nullptr) {
if (A->val <= B->val) {
result->next = A;
A = A->next;
} else {
result->next = B;
B = B->next;
}
result = result->next;
}
// 将最后一个遍历完的链表添加到结果链表的末尾
if (A != nullptr) {
result->next = A;
} else {
result->next = B;
}
return result;
}
int main() {
// 创建示例顺序表
ListNode* A = new ListNode(1);
A->next = new ListNode(3);
A->next->next = new ListNode(5);
ListNode* B = new ListNode(2);
B->next = new ListNode(4);
B->next->next = new ListNode(6);
// 合并两个列表
ListNode* C = mergeTwoLists(A, B);
// 打印合并后的列表C
while (C != nullptr) {
cout << C->val << " ";
C = C->next;
}
return 0;
}
```
这个程序首先检查A和B的头结点的大小,然后递归地比较并选择较小的元素,直到其中一个链表遍历完。最后把剩下的部分添加到结果链表的末尾。