将单链表中重复的元素删除，每个重复元素只保留一个

方法一：使用哈希表

算法思路：

1.创建一个哈希表，用于存储链表中每个元素的出现次数。

2.遍历链表，如果当前元素的出现次数大于1，则删除该元素。

3.如果当前元素的出现次数为1，则将该元素的出现次数加1。

4.返回链表的头节点。

算法实现：

C++ 代码

ListNode* deleteDuplicates(ListNode* head) {
    if (head == NULL) return NULL;
    unordered_map<int, int> mp;
    ListNode* curr = head;
    while (curr != NULL) {
        mp[curr->val]++;
        curr = curr->next;
    }
    ListNode* prev = NULL;
    curr = head;
    while (curr != NULL) {
        if (mp[curr->val] > 1) {
            if (prev == NULL) {
                head = curr->next;
            } else {
                prev->next = curr->next;
            }
            ListNode* temp = curr;
            curr = curr->next;
            delete temp;
        } else {
            prev = curr;
            curr = curr->next;
        }
    }
    return head;
}

Python 代码

def deleteDuplicates(self, head: ListNode) -> ListNode:
    if head is None:
        return None
    mp = {}
    curr = head
    while curr is not None:
        if curr.val not in mp:
            mp[curr.val] = 1
        else:
            mp[curr.val] += 1
        curr = curr.next
    prev = None
    curr = head
    while curr is not None:
        if mp[curr.val] > 1:
            if prev is None:
                head = curr.next
            else:
                prev.next = curr.next
            temp = curr
            curr = curr.next
            del temp
        else:
            prev = curr
            curr = curr.next
    return head

方法二：使用双指针

算法思路：

1.定义两个指针prev和curr，分别指向链表的前一个节点和当前节点。

2.遍历链表，如果当前节点的值与下一个节点的值相同，则删除下一个节点。

3.如果当前节点的值与下一个节点的值不同，则将prev指向当前节点，将curr指向下一个节点。

4.返回链表的头节点。

算法实现：

C++ 代码

ListNode* deleteDuplicates(ListNode* head) {
    if (head == NULL) return NULL;
    ListNode* prev = head;
    ListNode* curr = head->next;
    while (curr != NULL) {
        if (prev->val == curr->val) {
            prev->next = curr->next;
            ListNode* temp = curr;
            curr = curr->next;
            delete temp;
        } else {
            prev = curr;
            curr = curr->next;
        }
    }
    return head;
}

Python 代码

def deleteDuplicates(self, head: ListNode) -> ListNode:
    if head is None:
        return None
    prev = head
    curr = head.next
    while curr is not None:
        if prev.val == curr.val:
            prev.next = curr.next
            temp = curr
            curr = curr.next
            del temp
        else:
            prev = curr
            curr = curr.next
    return head

时间复杂度：O(n)

空间复杂度：O(1)