题解 | #删除有序链表中重复的元素-II#

public ListNode deleteDuplicates (ListNode head) {
      //当是单个或者为空的元素的情况
      if(head==null||head.next==null){
          return head;
      }
      //哨兵
      ListNode numpy =  new ListNode(-1);
      ListNode node = numpy;
      //前一个元素
      ListNode nodePre = head;
      //后一个元素
      ListNode nodeNext = head.next;
      //记录重复的元素是什么
      int value = Integer.MAX_VALUE;

      while(nodeNext!=null){
          //入锅存在前一个元素和后一个元素相同的情况，记录下来当前元素的值
          if(nodePre.val == nodeNext.val){
              value = nodePre.val;
          }
          //当pre指针不是重复的值的时候，才能让哨兵指向他
   //假设1，2，2，3，如果只通过pre和next不重复判断，当2，3不重复的时候，哨兵指向2
          else if(nodePre.val!=value){
               node.next = nodePre;
               node = node.next;
          }
          nodePre = nodePre.next;
          nodeNext = nodeNext.next;
      }
        //这里不太好理解：
 //假设是1，2，2，3这样的情况，
 //上述循环的终止是pre在3上，next为null，此刻3不是重复值，但是哨兵并没有指向它，会造成3的丢失
 //假设是1，2，2
 //上述循环的终止是pre在2上，next为null，此刻2是重复值，哨兵得指向null
 //因为哨兵第一次指向的是1，但是1没有断开和2，2的连线，当下一次循环的时候哨兵是1了，但是2，2重复了
 //所以node.next=null是为了断开末尾重复的情况
        if(nodePre.val!=value){
            node.next=nodePre;
        }
        else{
            node.next=null;
        }
        return numpy.next;
    }

public ListNode deleteDuplicates (ListNode head) {
        HashMap<Integer,Integer> map = new HashMap();
        ListNode nodeHead = head;
        ListNode numpy = new ListNode(-1);
        ListNode numpyRemeber = numpy;
        int count;
        while(nodeHead!=null){
            count = 0;
            if(map.containsKey(nodeHead.val)){
               count = map.get(nodeHead.val);
            }
            map.put(nodeHead.val,count+1);
            nodeHead = nodeHead.next;
        }
        nodeHead = head;
        while(nodeHead!=null){
            if(map.get(nodeHead.val)==1){
                numpyRemeber .next = nodeHead;
              numpyRemeber  = numpyRemeber .next;
            }
            nodeHead= nodeHead.next;
        }
 //这里是避免出现1，2，2这样的重复值在末尾的情况，因为在循环中对重复是不进行操作的
        numpyRemeber.next = null;
        return numpy.next;
    }