删除链表中重复的结点（java版）

【题目描述】在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

---

【解题思路1】 //1. 遍历当前链表，用linkedHashMap存储每个结点的出现次数。 //2. 再次遍历原链表，只连接出现次数为1的节点。 //3. 设置一个标志，用来设置头结点，防止头结点即重复的情况。

import java.util.LinkedHashMap; public class Solution { public ListNode deleteDuplication(ListNode pHead) { if(pHead==null){ return null; } boolean flag = true; ListNode inx=pHead, current=null; LinkedHashMap <Integer, Integer> map = new LinkedHashMap<Integer, Integer>(); while(inx!=null){ if(map.containsKey(inx.val)){ map.put(inx.val, map.get(inx.val)+1); }else{ map.put(inx.val, 1); } inx = inx.next; } inx = pHead; pHead = null; //重新置空，适用于所有结点值都相同的情况 while(inx != null){ if(flag==true && map.get(inx.val)==1){ //设置头结点 pHead = inx; current = inx; flag = false; }else if(flag==false && map.get(inx.val)==1){ current.next = inx; current = inx; } inx = inx.next; } if(current != null){ current.next = null; //去掉尾巴，适用于最后的几个结点重复的情况 } return pHead; } }

---

【解题思路2】 //1.把当前结点的前一个结点（pre）和后面值比当前结点的值要大的结点相连。

public class Solution {     public ListNode deleteDuplication(ListNode pHead)     {         if(pHead == null || pHead.next == null) return pHead;         ListNode temp = new ListNode(-1);         temp.next = pHead;         ListNode curNode = pHead;         ListNode pre = temp;          while(curNode != null && curNode.next != null){             ListNode next = curNode.next;             if(curNode.val == next.val){                 while(next != null && curNode.val == next.val){                     next = next.next;                 }                 pre.next = next;                 curNode = next;             }else{                 pre = curNode;                 curNode = curNode.next;             }         }         return temp.next;     } }