解法一：哈希

1、思路

• 用两个指针pre与cur一前一后遍历链表，同时将cur节点的值存入哈希表中，若cur的值已存在，则跳过cur这个节点。

• 时间复杂度与空间复杂度均为 $O(N)$。

2、代码

class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;

        unordered_set<int> hash;
        hash.insert(head->val);                 //先把头结点的值插入哈希表

        auto pre = head;

        while (pre->next != nullptr)
        {
            auto cur = pre->next;
            if (hash.find(cur->val) == hash.end())
            {
                hash.insert(cur->val);          //cur值插入哈希表
                pre = pre->next;
            }
            else
            {
                pre->next = pre->next->next;    //跳过cur节点
            }
        }

        return head;
    }
};

解法二：暴力双循环

1、思路

• 用两重循环来找重复节点，找到就跳过；

• 时间复杂度最坏为 $O(N^2)$，空间复杂度为 $O(1)$。

2、代码

class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;

        auto pre = head;
        while (pre != nullptr)
        {
            auto cur = pre;
            while (cur->next != nullptr)
            {
                if (cur->next->val == pre->val)     //与第一重循环的pre相同则跳过
                {
                    cur->next = cur->next->next;
                }
                else
                {
                    cur = cur->next;
                }
            }

            pre = pre->next;
        }

        return head;
    }
};