题目描述
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
OJ链接:https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef
解法1 带头节点的解法
/* 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; } }