用Dec C++编写程序:将两个有序链表合并,要求合并后无重复数据
时间: 2024-09-25 14:07:06 浏览: 34
C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现
在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(0); // 创建虚拟头节点
ListNode* tail = &dummy; // 尾指针指向虚拟头
while (l1 != NULL && l2 != NULL) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else if (l1->val > l2->val) {
tail->next = l2;
l2 = l2->next;
} else { // 如果值相等,只添加一次
tail->next = l1;
l1 = l1->next;
}
tail = tail->next;
}
// 添加剩余未处理的链表部分,如果其中一个为空,直接连接另一个
if (l1 != NULL)
tail->next = l1;
else
tail->next = l2;
return dummy.next; // 返回结果,去掉虚拟头节点
}
int main() {
// 测试示例,创建两个有序链表
ListNode* list1 = new ListNode(1);
list1->next = new ListNode(2);
list1->next->next = new ListNode(3);
ListNode* list2 = new ListNode(2);
list2->next = new ListNode(4);
list2->next->next = new ListNode(5);
// 合并并打印结果
ListNode* mergedList = mergeTwoLists(list1, list2);
while (mergedList != NULL) {
cout << mergedList->val << " ";
mergedList = mergedList->next;
}
cout << endl;
delete list1;
delete list2;
return 0;
}
```
阅读全文