题目链接：删除链表中重复的结点_牛客题霸_牛客网
注意点：
1.考虑头节点重复，所以构造虚拟头节点
1.方法一参考了评论区：申请两个指针的pre和cur,pre指向cur的前一个节点，cur指向当前节点，如果cur和cur->next的val想等，就循环找出所有重复节点的末尾，然后pre跳到不重复的节点上即可，时间和空间复杂度都是O(n)。
2.方法二：哈希去重，记录每个节点出现的次数，大于1的指向下一个节点
目录
方法一：双指针
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead) {
if (!pHead) return NULL;
//创建虚拟头节点，防止第一个节点就重复的问题
ListNode* nhead = new ListNode(0);
nhead->next = pHead;
ListNode* pre= nhead, *cur = pHead;
while(cur){
//相邻节点值相等
if(cur ->next && cur->val == cur->next->val){
//找出所有的相同节点
while(cur->next && cur->val == cur->next->val){
cur = cur->next;
}
cur = cur->next;
//跳过重复节点链接
pre ->next = cur;
}
else{
pre = cur;
cur = cur->next;
}
}
return nhead->next;
}
};方法二：哈希
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead) {
if (!pHead) return NULL;
//创建虚拟头节点，防止第一个节点就重复的问题
ListNode* nhead = new ListNode(0);
nhead->next = pHead;
ListNode *cur = nhead;
//记录每个节点的个数
unordered_map<int, int> map;
while(cur){
map[cur->val]++;
cur = cur->next;
}
//重新遍历链表，删除重复元素
cur = nhead;
while(cur->next){
if(map[cur->next->val] != 1){
//跳过重复元素
cur->next = cur->next->next;
}else{
cur = cur->next;
}
}
//返回头节点
return nhead->next;
}
};
