Removing Duplicates from a Linked List

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

Related Tags:

Clarification Questions

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

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() {

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

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> 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());
}

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> 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!