在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
OJ链接:https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode pHead){
if(pHead == null)
return pHead;
//为了简单,构造一个有头结点的链表
ListNode head = new ListNode(0);
head.next = pHead;//带头节点的链表的next指向pHead,我们返回的时候就返回head.next即可
//prev永远在last的前面
ListNode prev = head;//前指针 目的:永远指向的是重复节点的前一个节点,为了方便删除
ListNode last = prev.next;//后指针
while(last!=null ){
//1、,先找到重复的开始
//如果last和last.next不相等,就一直让prev和last往后走
while(last.next != null && last.val!= last.next.val){
prev = prev.next;
last = last.next;
}
//2、再找到重复的范围
//如果last和last.next相等,就让last一直往后走,找和last.val相等的
while(last.next != null && last.val == last.next.val){
last=last.next;
}
//走到这里,结果一共有三种情况。注意:prev永远指向的是前驱有效起始节点:
/*
走到这里就构成了一个:(prev,last] 的区间
1、last.next != null 并且prev到last是一段重复的范围,prev.next=last.next
2、last.next == null 并且prev到last是一段重复的范围,prev.next=last.next(null)
3、last.next == null 整张链表没有重复节点
*/
if(prev.next != last){
prev.next = last.next;
}
//走到这一步,就是为了保证恢复和最开始一致
last = last.next;
}
//因为要把头节点给省略,所以这样做
return head.next;
}
}