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