本题为剑指offer面试题58
牛客网测试地址：https://www.nowcoder.com/questionTerminal/fc533c45b73a41b0b44ccba763f866ef
[编程题]删除链表中重复的结点 热度指数：63742 时间限制：1秒 空间限制：32768K 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
Java代码：
package go.jacob.day607; import go.jacob.day609.Demo5.ListNode; public class Demo2 { // 递归实现 public ListNode deleteDuplication_1(ListNode pHead) { // 递归停止条件 if (pHead == null || pHead.next == null) return pHead; ListNode current = pHead.next; // 如果pHead是重复元素 if (pHead.val == current.val) { current = current.next; while (current != null && current.val == pHead.val) current = current.next; pHead = current; return deleteDuplication_1(current); } else { // pHead不是重复元素 pHead.next = deleteDuplication_1(current); return pHead; } } //方法二：循环实现 public ListNode deleteDuplication_2(ListNode pHead) { if (pHead == null || pHead.next == null) return pHead; ListNode preNode = null; ListNode node = pHead; ListNode postNode = null; boolean needDel = false; while (node != null) { // 如果node不是最后一个节点 if (node.next != null) { postNode = node.next; //postNode为null或者val与node.val不同的第一个节点 while (postNode != null && postNode.val == node.val) { postNode = postNode.next; needDel = true; } } else //到链表结尾 postNode = null; // 如果node和postNode不同，即不需要进行删除操作 if (!needDel) { //如果第一个元素为空 if (preNode == null) { preNode = node; pHead = preNode; } else { preNode.next = node; preNode = node; } node = postNode; } else { node = postNode; needDel = false; if (postNode == null && preNode != null) preNode.next = null; } } return preNode == null ? null : pHead; } //方法三：循环实现:剑指offer解法 public ListNode deleteDuplication_3(ListNode pHead) { if(pHead==null||pHead.next==null) return pHead; ListNode pPreNode=null; ListNode pNode=pHead; while(pNode!=null){ ListNode pNext=pNode.next; boolean needDelete=false; if(pNext!=null&&pNext.val==pNode.val) needDelete=true; if(!needDelete){ pPreNode=pNode; pNode=pNode.next; }else{ int value=pNode.val; ListNode pToBeDel=pNode; while(pToBeDel!=null&&pToBeDel.val==value){ pNext=pToBeDel.next; pToBeDel=pNext; } if(pPreNode==null) pHead=pNext; else pPreNode.next=pNext; pNode=pNext; } } return pHead; } class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } }
