Remove Duplicates from Linked List

LinkedListRemoveDuplicates.java

 head->1->2->3->1->4->NULL
 
 head->1->2->3->4->NULL 
 
 
 Given a reference to the head of a linked list, write a function that removes duplicates.


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return head;
        
        ListNode curr = head;
        ListNode prev = null;
        HashSet<Integer> listSet= new HashSet<Integer>();
       
        while (curr != null){
            if (listSet.contains(curr.val)){
                ListNode temp = curr.next;
                prev.next = temp;
                curr = temp;
                
            }
            else{
                listSet.add(curr.val);
                prev = curr;
                curr = curr.next;
            }
        }
        return head;
    }
}



//Alternate problem:  remove all nodes that are duplicated
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
         if (head == null) return head;
         ListNode fakeHead = new ListNode(0);
         fakeHead.next = head;
        
        ListNode curr = head;
        ListNode prev = fakeHead;
       
        while (curr != null){
            while (curr.next != null && curr.val == curr.next.val){
                curr = curr.next;
            }
            
            if (prev.next == curr){
                prev = prev.next;
            }
            else{
                prev.next = curr.next;
            }
            
            curr = curr.next;
            
        }
        return fakeHead.next;
        
    }
}