利用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-27 20:11:14 浏览: 49
数据结构与算法 c++实现 两个单链表合并为一个单链表,两个表的元素交错排列,新表用原表结点的内存空间 按元素序列的奇偶分割单
5星 · 资源好评率100%
在C++中,你可以通过遍历两个链表,并比较当前节点的值来合并它们。由于不允许添加新的节点,我们需要直接修改现有的节点指针。以下是一个简单的示例程序:
```cpp
#include <iostream>
// 定义链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* LA, ListNode* LB) {
// 如果LA为空,返回LB
if (LA == NULL) return LB;
// 如果LB为空,返回LA
if (LB == NULL) return LA;
// 比较两个链表的头节点
if (LA->val <= LB->val) {
LA->next = mergeTwoLists(LA->next, LB); // 合并LA的剩余部分和LB
return LA;
} else {
LB->next = mergeTwoLists(LA, LB->next); // 合并LB的剩余部分和LA
return LB;
}
}
void printList(ListNode* head) {
while (head != NULL) {
std::cout << head->val << " ";
head = head->next;
}
std::cout << "\n";
}
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 = mergeTwoLists(LA, LB);
// 打印结果
printList(LC);
return 0;
}
```
当你运行这个程序,输出将会是`1 2 3 3 4 4 5 6`,这就是合并后的递增有序链表。
阅读全文