题解 | #删除有序链表中重复的元素-II#
删除有序链表中重复的元素-II
http://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024
题意：
方法：
计数数组
思路：首先，遍历链表统计各值出现的次数；
然后，遍历链表，将值出现的个数大于1的节点删除。
注意点：为了方便，这里给链表新增头结点。（因为删除某节点必须得知道某节点的前一个节点，防止删除是第一个节点的特例，所以额外新建头结点）
class Solution {
public:
unordered_map<int,int> mp;//计数数组
ListNode* deleteDuplicates(ListNode* head) {
ListNode *p=head;
while(p){
mp[p->val]++;//计数
p=p->next;
}
ListNode *h=new ListNode(0);
h->next=head;//新增头结点
p=h;
ListNode *q=head;
while(q){
if(mp[q->val]>1){//如果个数大于1，则删除
p->next=q->next;
q=q->next;
}else{
p=p->next;
q=q->next;
}
}
return h->next;
}
};
时间复杂度：%2C%E9%81%8D%E5%8E%86%E9%93%BE%E8%A1%A8%E3%80%82)
空间复杂度：%2C%E8%AE%A1%E6%95%B0map%E5%AD%98%E5%82%A8%E7%A9%BA%E9%97%B4%E3%80%82)
投递字节跳动等公司10个岗位
这样才显得专业
