题目描述
在一个排序的链表中,存在重复的节点,请删除该链表中重复的节点,重复的节点不保留。
数据范围
链表中节点 val 值取值范围 [0,100]。
链表长度 [0,100]。
样例
输入:1->2->3->3->4->4->5
输出:1->2->5
输入:1->1->1->2->3
输出:2->3
算法
(线性扫描) $O(n)$
C++ 代码
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
auto dummy = new ListNode(-1);
dummy->next=head;
auto p=dummy;
while(p->next){
auto q=p->next;
//第一位是p.next,q要么通过while走到第二位再执行if,要么走到后面了执行else
while(q && q->val==p->next->val){
q=q->next;
}
//if和else,if是p没有需要跳过的next不需要改所以就进入下一位p继续扫描,而else需要跳过,所以必须停在这里更新p的next
if(p->next->next==q){
p=p->next;
}
else{
p->next=q;
}
}
return dummy->next;
}
};
这道题是重复的都去掉,要用到dummy虚拟前表头一个,一个p代替dummy,p派出q勘测进行检测判断如何操作
而力扣83题,是去掉重复部分但保留1个。你可以也沿用此题的思路,不过q勘测用的while需要变一下使得q
停在最后一个重复元素上而不是忽略全部,而且后面的if条件也就是需要用到q这个要改变的东西也要注意改变