将两个递增的有序链表合并为一个递减的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间,表中不允许有重复的数据。 用C++编写
时间: 2024-10-11 21:03:58 浏览: 51
将两个递增排序的有序链表合并成一个递减的有序链表,可以采用双指针法,并利用原链表节点结构。以下是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* mergedHead = nullptr, *mergedTail = nullptr;
// 当l1和l2都不为空时
while (l1 && l2) {
// 如果l1的值小于等于l2的值,取l1的节点并更新l1
if (l1->val <= l2->val) {
if (!mergedHead) {
mergedHead = mergedTail = l1;
} else {
mergedTail->next = l1;
mergedTail = l1;
}
l1 = l1->next;
} else { // 否则取l2的节点并更新l2
if (!mergedHead) {
mergedHead = mergedTail = l2;
} else {
mergedTail->next = l2;
mergedTail = l2;
}
l2 = l2->next;
}
}
// 如果其中一个链表还有剩余元素,则直接连接到新的链表尾部
if (l1) {
mergedTail->next = l1;
} else {
mergedTail->next = l2;
}
return mergedHead;
}
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* result = mergeTwoLists(l1, l2);
// 打印合并后的链表(逆序)
while (result) {
cout << result->val << " ";
result = result->next;
}
return 0;
}
```
在这个例子中,我们遍历两个链表,每次都选择较大的节点添加到新链表中,直到遍历完其中一个链表。然后把另一个链表剩下的部分接到结果链表的尾部。
阅读全文