//https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

//Given a sorted linked list, delete all duplicates such that each element appear only once.

//1prepre
// : 2 ms, Remove Duplicates from Sorted ListJava57.30% 
// : 36.5 MB, Remove Duplicates from Sorted ListJava68.83% 

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return head;  // headnull
        ListNode p = head.next;
        ListNode pre = head;
        while( p != null ){
            if (pre.val == p.val){
                pre.next = p.next;
                p = p.next; 
            }
            else{
                pre = p;
                p = p.next;   
            }  
        }
        return head;
    }
}

//java.lang.NullPointerException
// if (head == null) return head;


//2set
// : 7 ms, Remove Duplicates from Sorted ListJava5.10% 
// : 36.3 MB, Remove Duplicates from Sorted ListJava75.05% 

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        Set set = new HashSet();
        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode p = head;
        
        while( p != null ){
            if (set.contains(p.val)){
                pre.next = p.next;
                p = p.next; 
            }
            else{
                set.add(p.val);
                pre = p;
                p = p.next;   
            }  
        }
        return head;
    }
}


//3
// : 3 ms, Remove Duplicates from Sorted ListJava6.53% 
// : 36.3 MB, Remove Duplicates from Sorted ListJava74.62% 
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode p = deleteDuplicates(head.next);
        if (head.val == p.val) head.next = p.next;
        return head;
    }
}

//1,headreturn
//2,
//3,head.next
//headhead.nexthead.nexthead