Remove duplicate nodes in an unsorted linked list

This is a very interesting coding question that is being asked a lot in coding interviews.

As a solution, we need to keep track of the elements we already visited, so that when we stumble upon an element with data we already have in our memory, we remove that node by setting the previous node to point to the current.next.
In that way, we just remove the node from the linked list and it will be removed by the GC on the next run since there are no longer any references pointing to it.

For the data structure, we'll be using the Set, since we can easily check if the set already contains an element using set.contains(Object o) method.

Removing duplicate nodes in an unsorted linked list

Below is the Java implementation of the proposed solution.
Note: We are using our custom implementation of the Linked List, that we defined here.

public void removeDuplicates() {
    if (head == null) {
        throw new RuntimeException("The list is empty");
    }

    Node<T> current = head;
    Node<T> previous = null; // need to keep track of the previous element
    Set<Integer> set = new HashSet<>();

    while (current != null) {
        if (set.contains(current.data)) {
            System.out.println("Removing duplicate number: " + current.data);
            previous.next = current.next;
        } else {
            set.add((Integer) current.data);
            previous = current;
        }

        current = current.next;
    }
}

That is all about how to remove duplicate nodes from unsorted linked list in Java.