删除排序链表中的重复元素 II

题目链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/

题解1：用Map记录哪个项是没有重复的

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
    Map<Integer,Integer> map = new LinkedHashMap<>();
    ListNode h = head;
    ListNode dummy = new ListNode(0);
    ListNode res = dummy;
    while(h != null){
        map.put(h.val,map.getOrDefault(h.val,0)+1);
        h = h.next;
    }
    for(Map.Entry<Integer,Integer> e : map.entrySet()){
        if(e.getValue() == 1){
            dummy.next = new ListNode(e.getKey());
            dummy = dummy.next;
        }
    }
    return res.next;
    }
}

题解2：三指针

先建一个dummy节点保证删除操作一致性，指针preL.next始终指向l，指针l在数据没有重复时指向指针r，如果l和r指向的数据相等，移动r指针，直至l和r指向数据不同，进行链表的常规删除操作preL.next指向r，l指向r，r也后移一位

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
   // Map<Integer,Integer> map = new LinkedHashMap<>();
    if(head == null) return null;
   // ListNode h = head;
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode preL = dummy,res = dummy;
    ListNode l = head, r = head.next;
   // if(r == null) return head;
    while(r != null){
       if(l.val == r.val){
           while(r != null && l.val == r.val){
               r = r.next;
           }
           preL.next = r;
           l = r;
           r = r== null? null : r.next;
       }else{
           preL = preL.next;
           l = l.next;
           r = r.next;
       }
    }
    return res.next;
    }
}