题解 | #删除链表中重复的结点#(哈希表）

发现《剑指offer》里很多的链表题都是需要用到各种模板类，哈希模板类是高频出现的内容，学校里教到STL基本的类就结束了，甚至连vector这类神器都是一笔带过。。
话不多说，上代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
#include <unordered_map>
#include <utility>
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if(pHead==nullptr)
        {
            return nullptr;
        }
        ListNode* cur = pHead;
        unordered_map<int, int>key;
        
        while(cur!=nullptr)
        {
            key[cur->val]++;
            cur=cur->next;
        }

        ListNode* res = new ListNode(0);
        res->next = pHead;
        cur = res;

        while(cur->next!=nullptr)
        {
            if(key[cur->next->val]!=1)
            {
                cur->next = cur->next->next;
            }
            else {
                cur = cur->next;
            }
        }
        return res->next;


        
    }
};

这题的核心思路就是利用哈希表中，可以使用值去查找内容的特性来找。
实际上大一刷ACM时也刷到过类似题目不过当然不是链表。一般是类似于给一组数，然后看某一数（例如5）出现了几次。那时候的想法就是

int a[100000] = {0};
for i to n:
	a[i]++;
cout<<a[key]<<endl;

当时还是觉得挺ok的，不过实际上会发现开个a[100000]这个数组，内存直接浪费。去面试这么写，绝对被鄙视（似乎我在某个交流平台下面看到过有人吐槽过新人的写代码能力）这类模板的使用至少不至于看的像个C++菜鸟。

在 unordered_map<int, int> 中，第一个 int 表示键的类型，而第二个 int 表示值的类型。

具体解释如下：

第一个 int：表示键的类型。在 unordered_map 中，键是用于唯一标识和访问元素的对象。在此示例中，键的类型为整数（int）。

第二个 int：表示值的类型。值是与每个键相关联的数据。在此示例中，值的类型也为整数（int）。

因此，unordered_map<int, int>
是一个将整数作为键和值的无序键值对存储结构。您可以根据实际需要，选择不同的类型作为键和值，以满足特定的应用场景。——chatGPT
一般来说，键的类型应该是能够提供唯一性并支持哈希函数计算的类型。常见的键的类型包括但不限于以下几种：

整数类型（如 int, long, unsigned int 等） 字符串类型（如 std::string, const char* 等）
枚举类型（如自定义的枚举类型） 自定义类/结构体（需要提供自定义的哈希函数和相等比较函数）
选择键的类型时，需要根据实际的数据和使用需求来决定。确保选择的类型能够满足对键唯一性和哈希函数计算的要求，并能够正确进行比较和查找操作。

需要注意的是，如果您使用自定义的类或结构体作为键的类型，就需要提供适当的哈希函数和相等比较函数来让 unordered_map 正确地进行元素查找和存储

也就是说也可以利用此类容器去存放字符串/指定类/指定结构体