Removing Duplicates from a Linked List

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

Related Tags:

Clarification Questions

• Is the list sorted?
• 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.

1) Already sorted in O(n) time

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

Complexity

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

``````public void removeDuplicatesSorting() {

// 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.

2) Using no buffer

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.

Complexity

Time: O(n2), Space: O(1)

``````public void removeDuplicatesTwoLoops() {

// O(n^2) complexity, but no buffer needed
// get a traversal node, then use a runner
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());
}
``````

3) Using a hashmap in O(n) time

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.

Complexity

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

``````public void removeDuplicatesHashedTable() {
Hashtable<E, Boolean> table = new Hashtable<>();

// Start at the head element
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: