写一算法讲单链表中值重复的结点删除,使所得的结果链表中所有结点的值均不相同,使用c++解决
时间: 2024-09-29 15:05:54 浏览: 9
为了实现这个功能,你可以使用哈希集合(unordered_set)来跟踪已经遇到过的值。遍历链表的同时,检查当前节点的值是否已经在集合中。如果不在,就将其添加到结果链表;如果在,说明有重复值,只需跳过该节点即可。下面是C++代码的一个简要描述:
```cpp
#include <iostream>
#include <unordered_set>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* removeDuplicates(ListNode* head) {
std::unordered_set<int> seenValues;
ListNode* prev = nullptr, *current = head;
while (current != nullptr) {
if (seenValues.find(current->val) == seenValues.end()) {
// 如果值未见过,加入结果链表并更新集合
seenValues.insert(current->val);
if (prev != nullptr) {
prev->next = current;
} else {
head = current;
}
prev = current;
} else {
// 遇到重复值,直接跳过
current = current->next;
}
}
return head;
}
int main() {
// 创建示例链表并删除重复值
ListNode* list = createLinkedList(); // 自行创建链表函数
ListNode* result = removeDuplicates(list);
// 打印结果链表
printLinkedList(result); // 自行实现打印链表函数
return 0;
}
```