用C++语言写出“有两个单链表LA和LB,其元素均为递增有序序列,将它们合并成一个单链表LC,要求LC也是递增有序序列,且不增加新结点。 如LA=(2,4,4,6),LB=(1,3,3,5),则LC=(1,2,3,3,4,4,5,6)。”的程序
时间: 2024-10-25 20:14:32 浏览: 18
在C++中,可以编写如下的函数来合并两个递增有序的单链表,同时保持列表的顺序且不创建新的节点。我们可以利用头插法的思想,从每个链表的头部开始比较,将较小的值移到合并后的链表中。
```cpp
#include <iostream>
// 定义链表节点结构
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 合并链表函数
ListNode* mergeSortedLists(ListNode* LA, ListNode* LB) {
if (LA == nullptr) return LB;
if (LB == nullptr) return LA;
// 如果LA的当前元素小于LB,就直接把LA的指针移动到下一个
if (LA->val <= LB->val) {
LA->next = mergeSortedLists(LA->next, LB);
return LA;
} else {
// 否则,把LB的当前元素移到LA的后面
LB->next = mergeSortedLists(LA, LB->next);
return LB;
}
}
int main() {
// 创建两个示例链表
ListNode* LA = new ListNode(2);
LA->next = new ListNode(4);
LA->next->next = new ListNode(4);
LA->next->next->next = new ListNode(6);
ListNode* LB = new ListNode(1);
LB->next = new ListNode(3);
LB->next->next = new ListNode(3);
LB->next->next->next = new ListNode(5);
// 合并两个链表
ListNode* LC = mergeSortedLists(LA, LB);
// 打印合并后的链表(仅用于演示,实际应用中不需要这一步)
while (LC != nullptr) {
std::cout << LC->val << " ";
LC = LC->next;
}
// 清理内存
for (auto* node = LA; node != nullptr; node = node->next) delete node;
for (auto* node = LB; node != nullptr; node = node->next) delete node;
return 0;
}
```
当你运行这个程序时,会输出"1 2 3 3 4 4 5 6",这就是合并后的链表。
阅读全文