# Write code to remove duplicates from an unsorted linked list

QUESTION:

Remove Dups: Write code to remove duplicates from an unsorted linked list.
How would you solve this problem if a temporary buffer is not allowed?

SOLUTION:

• In order to remove duplicates from a linked list, we need to be able to track duplicates.
• A simple hash table will work well here.

In the below solution, we simply iterate through the linked list, adding each element to a hash table. When we discover a duplicate element, we remove the element and continue iterating. We can do this all in one pass since we are using a linked list.

```void deleteDups(LinkedListNode n) {
HashSet<Integer> set = new HashSet<Integer>();
while (n != null) {
if (set.contains(n.data)) {
previous.next = n.next;
} else {
previous = n;
}
n = n.next;
}
} ```

The above solution takes O(N) time, where N is the number of elements in the linked list.

lf we don’t have a buffer, we can iterate with two pointers: current which iterates through the linked list, and runner which checks all subsequent nodes for duplicates.

lf we don’t have a buffer, we can iterate with two pointers: current which iterates through the linked list, and runner which checks all subsequent nodes for duplicates.

```void deleteDups(LinkedListNode head) {
while (current != null) {

/* Remove all future nodes that have the same value */