两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另占用其他的存储空间,表中允许有重复的数据,用C++程序实现
时间: 2024-09-18 08:14:12 浏览: 23
这是一个经典的链表操作问题,可以使用迭代或递归的方式解决。下面是一个简单的C++解决方案,使用了迭代方法:
```cpp
#include <iostream>
// 定义链表节点结构
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 初始化头指针和当前指针
ListNode dummy(0);
ListNode* current = &dummy;
while (l1 != NULL && l2 != NULL) {
if (l1->val <= l2->val) { // 如果l1的值小或相等
current->next = l1; // 将l1链接到current之后
l1 = l1->next;
} else { // 否则,将l2链接到current之后
current->next = l2;
l2 = l2->next;
}
current = current->next; // 移动current指向下一个位置
}
// 如果其中一个链表还有剩余元素,将其连接到最后
if (l1 != NULL) {
current->next = l1;
} else {
current->next = l2;
}
return dummy.next; // 返回新链表的第一个节点
}
int main() {
// 创建两个示例链表
ListNode* l1 = new ListNode(1);
l1->next = new ListNode(2);
l1->next->next = new ListNode(4);
ListNode* l2 = new ListNode(1);
l2->next = new ListNode(3);
l2->next->next = new ListNode(4);
// 合并链表
ListNode* mergedList = mergeTwoLists(l1, l2);
// 打印合并后的链表
ListNode* temp = mergedList;
while (temp != nullptr) {
std::cout << temp->val << " ";
temp = temp->next;
}
std::cout << std::endl;
// 清理内存
delete l1;
delete l2;
return 0;
}
```
在这个程序中,我们创建了一个虚拟头节点`dummy`,用于简化合并过程。然后比较两个链表的当前节点值,将较小的节点添加到新链表中,并更新指针。最后返回`dummy.next`,得到合并后的链表。