编写一个删除单链表中多余的和值x相同的结点算法。
时间: 2024-05-15 20:15:26 浏览: 73
1. 定义一个指针pre指向当前结点的前一个结点,一个指针cur指向当前结点,一个指针head指向单链表头结点。
2. 定义一个哈希表,用于存储每个和值出现的次数。
3. 遍历单链表,统计每个和值出现的次数,并将其存储到哈希表中。
4. 再次遍历单链表,如果当前结点的和值在哈希表中的出现次数大于1,则将该结点从单链表中删除,即pre的next指向cur的next,cur指向下一个结点。
5. 最后返回单链表头结点head。
代码实现:
```
void removeDuplicates(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return;
}
unordered_map<int, int> mp; // 哈希表
ListNode* pre = head;
ListNode* cur = head->next;
mp[head->val] = 1; // 将头结点的值加入哈希表中
while (cur != nullptr) {
mp[cur->val]++;
if (mp[cur->val] > 1) { // 如果当前结点的和值在哈希表中的出现次数大于1
pre->next = cur->next; // 将该结点从单链表中删除
cur = pre->next;
} else {
pre = cur;
cur = cur->next;
}
}
}
```
阅读全文