题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表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; } }
