leetcode 链接：移除重复节点
《程序员面试代码指南》by 左程云 中相同题目：★☆☆☆删除无序列表中值重复出现的节点

题目

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例：

 输入：[1, 2, 3, 3, 2, 1]
 输出：[1, 2, 3]
 输入：[1, 1, 1, 1, 2]
 输出：[1, 2]

解答 & 代码

方法一：哈希表

使用额外的存储空间——哈希表，时间复杂度为 O(N)，额外空间复杂度为 O(N)

方法：遍历链表节点

• 如果该节点的值在哈希表中存在，则删除该节点
• 如果该节点的值在哈希表中不存在，则将该值插入哈希表

注：对于链表，为了避免一些 bug，可以增加一个虚拟头节点，即 dummyHead

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

#include <unordered_set>

class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        unordered_set<int> valMap;

        ListNode* dummyHead = new ListNode(0);    //虚拟头节点
        dummyHead->next = head;

        ListNode* cur = dummyHead->next;
        ListNode* pre = dummyHead;
        while(cur != NULL)
        {
            if(valMap.find(cur->val) != valMap.end())
            {
                pre->next = cur->next;
                delete cur;
                cur = pre->next;
            }
            else
            {
                valMap.insert(cur->val);
                pre = cur;
                cur = cur->next;
            }
        }
        return dummyHead->next;
    }
};

执行结果：

执行结果：通过

执行用时：48 ms, 在所有 C++ 提交中击败了 38.75% 的用户
内存消耗：16.3 MB, 在所有 C++ 提交中击败了 31.12% 的用户

方法二：暴力解法（时间换空间）

不使用额外的空间，时间复杂度为 O()，额外空间复杂度为 O(1)

遍历链表的节点，设当前遍历到的节点为 cur

• 遍历 cur 节点之前的节点
  • 如果有等值节点存在，说明 cur 节点是重复节点，应删除
  • 否则，cur = cur->next ```cpp /**
    • Definition for singly-linked list.
    • struct ListNode {
    • int val;
    • ListNode *next;
    • ListNode(int x) : val(x), next(NULL) {}
    • }; */

class Solution { public: ListNode removeDuplicateNodes(ListNode head) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head;

    ListNode* cur = dummyHead->next;
    ListNode* pre = dummyHead;
    while(cur != NULL)
    {
        // 遍历当前节点之前的节点，判断当前节点是否为重复节点
        ListNode* left = dummyHead->next;
        while(left != cur && left->val != cur->val)
        {
            left = left->next;
        }

        if(left != cur) // 说明前面有该值的节点，即当前节点为重复节点，应删除
        {
            pre->next = cur->next;
            delete cur;
            cur = pre->next;
        }
        else            // 当前节点不是重复节点
        {
            pre = cur;
            cur = cur->next;
        }
    }
    return dummyHead->next;
}

};

执行结果：

执行结果：通过

执行用时：500 ms, 在所有 C++ 提交中击败了 7.38% 的用户 内存消耗：14.9 MB, 在所有 C++ 提交中击败了 73.22% 的用户 ```