Remove Duplicates from Unsorted List

LintCode-217.Remove Duplicates from Unsorted List

Write code to remove duplicates from an unsorted linked list.

Example

Given 1->3->2->1->4.

Return 1->3->2->4

Challenge

(hard) How would you solve this problem if a temporary buffer is not allowed? In this case, you don't need to keep the order of nodes.

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: head node
     */
    public ListNode removeDuplicates(ListNode head) { 
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        
        ListNode prev = dummy, current = head;
        Set<Integer> map = new HashSet<>();

        while (current != null) {
            if (map.contains(current.val)) {
                prev.next = current.next;
                current = prev.next;
            } else {
                map.add(current.val);
                prev = current;
                current = current.next;
            }
        }
        
        return dummy.next;
    }  
}

Hope this helps,
Michael