LC1836. 从未排序的链表中移除重复元素

给定一个链表的第一个节点 head ，找到链表中所有出现多于一次的元素，并删除这些元素所在的节点。

返回删除后的链表。

示例 1:

img

输入: head = [1,2,3,2]
输出: [1,3]
解释: 2 在链表中出现了两次，所以所有的 2 都需要被删除。删除了所有的 2 之后，我们还剩下 [1,3] 。

示例 2:

img

输入: head = [2,1,1,2]
输出: []
解释: 2 和 1 都出现了两次。所有元素都需要被删除。

示例 3:

img

输入: head = [3,2,2,1,3,2,4]
输出: [1,4]
解释: 3 出现了两次，且 2 出现了三次。移除了所有的 3 和 2 后，我们还剩下 [1,4] 。

提示：

• 链表中节点个数的范围是 [1, 105]
• 1 <= Node.val <= 105

#include <unordered_map>

class Solution {
public:
    ListNode* deleteDuplicatesUnsorted(ListNode* head) {
        std::unordered_map<int, int> count;
        // 先遍历一遍链表，记录每个值出现的次数
        ListNode* p = head;
        while (p != nullptr) {
            count[p->val]++;
            p = p->next;
        }

        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        // 再遍历一遍节点，把重复出现的节点剔除
        p = dummy;
        while (p->next != nullptr) {
            ListNode* unique = p->next;
            // 删除重复节点直到找到不重复的节点
            while (unique != nullptr && count[unique->val] > 1) {
                ListNode* temp = unique;
                unique = unique->next;
                delete temp;  // 释放重复节点的内存
            }
            
            // 接入不重复的节点或尾部空指针
            if (unique == nullptr) {
                p->next = nullptr;
                break;
            } else {
                p->next = unique;
            }
            // p 前进，继续寻找不重复节点
            p = p->next;
        }

        // 保存结果并释放哑节点
        ListNode* result = dummy->next;
        delete dummy;
        return result;
    }
};