已知一个双向链表,编写算法删除表中所有重复的元素(需预先创建符合要求的双向链 表)。
时间: 2024-02-01 10:14:43 浏览: 67
双向链表删除重复元素的算法步骤如下:
1. 定义一个哈希表用来记录每个元素的出现次数。
2. 遍历双向链表中的每个元素,统计每个元素出现的次数。
3. 再次遍历双向链表,对于每个元素,如果它在哈希表中的出现次数大于1,则删除该节点。
4. 返回删除重复元素后的双向链表。
具体实现如下:
```
struct Node {
int val;
Node* prev;
Node* next;
Node(int x): val(x), prev(nullptr), next(nullptr) {}
};
Node* deleteDuplicates(Node* head) {
if (!head || !head->next) return head;
unordered_map<int, int> count; // 记录每个元素的出现次数
Node* curr = head;
while (curr) {
count[curr->val]++;
curr = curr->next;
}
Node* dummy = new Node(0); // 创建一个新的头结点
dummy->next = head;
head->prev = dummy;
curr = head;
while (curr) {
if (count[curr->val] > 1) { // 如果当前节点的值出现次数大于1,则删除该节点
curr->prev->next = curr->next;
if (curr->next) curr->next->prev = curr->prev;
delete curr;
curr = curr->prev;
}
curr = curr->next;
}
return dummy->next; // 返回删除重复元素后的链表
}
```
时间复杂度为 $O(n)$,其中 $n$ 是双向链表的长度。空间复杂度为 $O(n)$,需要额外使用哈希表记录每个元素的出现次数。
阅读全文