C++编写代码,移除未排序链表中的重复节点。保留最开始出现的节点
时间: 2024-09-27 14:05:37 浏览: 24
在C++中,你可以使用哈希集合(unordered_set)配合迭代器来去除一个单链表中的重复节点。以下是实现这个功能的一个简单示例:
```cpp
#include <iostream>
#include <unordered_set>
using namespace std;
// 定义链表节点结构
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// 移除链表中的重复节点
ListNode* removeDuplicates(ListNode* head) {
unordered_set<int> seen; // 存储已见过的值
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
if (seen.find(curr->val) == seen.end()) { // 如果当前值未见过
seen.insert(curr->val); // 添加到已见值集合
prev = curr; // 更新prev指针到当前节点
} else {
// 如果当前值重复,则删除它
ListNode* toDelete = curr;
curr = curr->next;
prev->next = curr;
delete toDelete;
}
}
return head;
}
// 打印链表
void printList(ListNode* head) {
while (head != nullptr) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
int main() {
// 创建一个有重复节点的链表示例
ListNode* list = new ListNode(1);
list->next = new ListNode(2);
list->next->next = new ListNode(3);
list->next->next->next = new ListNode(4);
list->next->next->next->next = new ListNode(2);
list->next->next->next->next->next = new ListNode(5);
// 移除重复节点并打印结果
list = removeDuplicates(list);
printList(list);
return 0;
}
```
在这个例子中,我们遍历链表,如果遇到的节点值已经存在于`seen`集合中,就删除该节点;否则将节点值添加到集合中,并更新前驱节点的`next`指针。