Remove Duplicates from Unsorted List(lintcode 217)

Description

Write code to remove duplicates from an unsorted linked list.

Example

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

Return 1->3->2->4.

Interface

/**
 * 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) { 
        // Write your code here
    }  
}

Idea

Use HashSet to save the numbers that have already appeared. We use head.next as the while-loop condition in order to delete the ListNode. Before the while-loop we have to set head == dummy. Otherwise, the value of head won't appear in the HashSet.

Solution

/**
 * 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) { 
        // Write your code here
        if (head == null) {
            return head;
        }
        HashSet set = new HashSet();
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        while (head.next != null) {
            if (set.contains(head.next.val)) {
                head.next = head.next.next;
            } else {
                set.add(head.next.val);
                head = head.next;
            }
        }
        return dummy.next;
    }  
}