写一算法讲单链表中值重复的结点删除,使所得的结果链表中所有结点的值均不相同
时间: 2024-09-29 09:05:28 浏览: 13
要删除单链表中重复的节点并保持结果链表中所有节点的值唯一,你可以使用哈希集合(HashSet或HashMap,取决于语言的具体实现)辅助完成此操作。以下是使用Python实现的一个示例算法:
```python
def delete_duplicates(head):
if not head or not head.next:
return head
# 使用哈希集合记录已遇见的值
seen = set()
current = head
while current:
if current.val in seen:
# 如果当前节点值已经存在,则删除它
next_node = current.next
current.next = None
current = next_node
else:
# 将当前节点的值添加到哈希集合中
seen.add(current.val)
current = current.next
return head
```
这个算法的工作原理是遍历链表,如果遇到的节点值已经在哈希集合中,就将当前节点从链表中移除;如果没有,就将其值添加到哈希集合中并继续遍历。最后返回处理后的头节点。
相关问题
写一算法讲单链表中值重复的结点删除,使所得的结果链表中所有结点的值均不相同,使用c++解决
为了实现这个功能,你可以使用哈希集合(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;
}
```
写一算法将单链表中值重复的结点删除,使所得的结果链表中所有结点的值均不相同。
算法如下:
1. 定义一个哈希表,用于存储链表中出现过的值。
2. 遍历单链表,对于每个结点,判断其值是否在哈希表中出现过。
3. 如果该值已经出现过,则将该结点从链表中删除。
4. 如果该值没有出现过,则将该值加入哈希表中,并继续遍历下一个结点。
5. 遍历完成后,所得的结果链表中所有结点的值均不相同。
6. 返回结果链表。
代码实现:
```
void removeDuplicates(ListNode* head) {
unordered_set<int> hashSet;
ListNode* curr = head;
ListNode* prev = nullptr;
while (curr != nullptr) {
if (hashSet.count(curr->val)) {
prev->next = curr->next;
delete curr;
curr = prev->next;
} else {
hashSet.insert(curr->val);
prev = curr;
curr = curr->next;
}
}
}
```