**Question:** Remove all duplicates that occur in a linked list.

Related Tags:

- Is the list sorted?
- Do we have access to an outside buffer?
- Is this a singly linked list?

Depending on the answer to these questions, we can solve this problem in three different ways. We'll assume a singly linked list.

If the list is sorted, we can solve this in one pass.

Time: `O(n)`, Space: `O(1)`

```
public void removeDuplicatesSorting() {
// Assume already sorted
Node<E> prev = this.head;
// Start at the second node
Node<E> current = prev.getNext();
while (current != null) {
// Found duplicate nodes
if (prev.getData().equals(current.getData())) {
prev.setNext(current.getNext());
} else {
prev = prev.getNext();
}
current = current.getNext();
}
System.out.println("Removed duplicates: " + this.toString());
}
```

If the list is not sorted, we can sort with mergesort in `O(n lg n)` time.

In the case we cannot use a buffer (space is limited), we must use two pointers - one slow and one fast. There will be two loops to this solution, so it will take `O(n) ^{2}` time.

The outer loop will have the slow runner pin down on one node. The fast runner will proceed to iterate through each node. If the fast runner's data is the same as that of the slow runner's, then we can delete.

Time: `O(n ^{2})`, Space:

```
public void removeDuplicatesTwoLoops() {
// O(n^2) complexity, but no buffer needed
// get a traversal node, then use a runner
Node<E> n = this.head;
Node<E> runner;
while (n != null) {
// n stays on one node, while runner traverses each proceeding node
runner = n;
// Keep running til end
while (runner.getNext() != null) {
// If runner node and n are the same, remove
if (runner.getNext().getData().equals(n.getData())) {
runner.setNext(runner.getNext().getNext());
} else {
runner = runner.getNext();
}
}
n = n.getNext();
}
System.out.println("Removed duplicates: " + this.toString());
}
```

We can use a hashmap and store variables already encountered. If we encounter a linked list with data that's already in our hash, we delete it. This takes `O(n)` time since it takes just one pass.

Time: `O(n)` Space: `O(n)`

```
public void removeDuplicatesHashedTable() {
Hashtable<E, Boolean> table = new Hashtable<>();
// Start at the head element
Node<E> n = this.head;
Node<E> previous = null;
while (n != null) {
// If the data stored is in our table, remove
if (table.containsKey(n.getData())) {
System.out.println("Removed duplicate: " + n.getData());
previous.setNext(n.getNext());
// Otherwise add data to the hashtable
} else {
table.put(n.getData(), true);
previous = n;
}
// Next node
n = n.getNext();
}
System.out.println("Removed duplicates: " + this.toString());
}
```

Came up with a better solution or have a question? Comment below!

Next Challenge: Removing Duplicates from a Linked List