用c++写一个程序,将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据。
时间: 2024-10-08 21:01:29 浏览: 22
你可以使用C++来编写一个函数,这个函数接受两个递增有序的链表的头节点作为输入,并返回合并后的链表的头节点。下面是一个简单的实现思路:
```cpp
#include <iostream>
using namespace std;
// 链表节点结构体
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 使用临时指针表示当前合并点
ListNode* dummy = new ListNode(0); // 创建虚拟头节点
ListNode* tail = dummy; // 尾部指针始终指向合并后的最后一个元素
while (l1 && l2) { // 当两个链表都有剩余元素时
if (l1->val <= l2->val) { // 如果l1的值小,将其添加到新链表
tail->next = l1;
l1 = l1->next;
} else { // 如果l2的值小,将其添加到新链表
tail->next = l2;
l2 = l2->next;
}
tail = tail->next; // 更新尾部指针
}
// 如果其中一个链表已经遍历完,将另一个链表剩下的部分追加到新链表末尾
if (l1)
tail->next = l1;
else
tail->next = l2;
return dummy->next; // 返回合并后的链表头节点
}
// 测试示例
int main() {
// 创建两个示例链表
ListNode* list1 = new ListNode(1);
list1->next = new ListNode(3);
list1->next->next = new ListNode(5);
ListNode* list2 = new ListNode(2);
list2->next = new ListNode(4);
list2->next->next = new ListNode(6);
// 合并并打印结果
ListNode* mergedList = mergeTwoLists(list1, list2);
while (mergedList) {
cout << mergedList->val << " ";
mergedList = mergedList->next;
}
return 0;
}
```
阅读全文