写一算法将单链表中值重复的结点删除,使所得的结果链表中所有结点的值均不相同。
时间: 2023-04-27 12:03:24 浏览: 189
删除单链表中值相同的多余结点-算法与数据结构--张乃孝-前三章习题课
算法如下:
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;
}
}
}
```
阅读全文