给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
解
三个指针 cur用来记录已经纳入新链表的尾部
a记录发现的新值(可能会被纳入答案链表)
b用来从新值(a)出发向后遍历
每走一步count+1 ,直到值不等于a的值。
若b走到不等于a的值时 count为1 ,说明a可以被纳入答案链表 同时更新 cur a b
若count不为1 ,说明a所在的节点不可以被纳入新链 ,则令a跳转到b此时所在 ,继续寻找
注意利用哑结点简化开始的处理 以及最后的结尾处理
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(Integer.MAX_VALUE);
dummy.next = head;
ListNode cur = dummy;
ListNode a = head;
ListNode b = head;
int count =0 ;
if(head==null)return head;
while(a.next!=null){
while(b.val==a.val){
if(b.next!=null){
count++;
b=b.next;
continue;
}else{
cur.next = null;
return dummy.next;
}
}
if(count==1){
cur.next=a;
a=b;
cur=cur.next;
count = 0;
}else{
a=b;
count = 0;
}
}
if(count==0)
cur.next=a;
return dummy.next;
}