Remove duplicates from an unsorted singly linked list causing logical error while trying to skip the repeated element

Question

I used auxiliary data structure "HashSet" to solve this problem. The logic is that I created a HashSet with non-repetitive elements and then while going through each node in my linked-list, checked if that item is in the hashSet. If it is there, I removed the data from the HashSet iterated through the linked list. The code and the logical error should be pretty self explanatory. I am just not able to skip the element in the list for the linked list that I have created in the main method.

import java.util.HashSet;

class Node{
    int value;
    Node next;

public Node(int value){
    this.value = value; 
    next = null;
}
public Node deleteNode(Node headNode){
    Node current = headNode;
    HashSet<Integer> setContainer = new HashSet<Integer>();
    while (current.next != null){
        setContainer.add(current.value);
        current = current.next;
    }
    current = headNode; // reset current to the headNode

    while (!setContainer.isEmpty()){
        if (current.next == null){
            return headNode;
        }
        if (current == headNode){
            setContainer.remove(current.value);
            current = current.next;
            //System.out.println(setContainer); Test
            continue;
        }
        if (!setContainer.contains(current.next.value)){
            current.next = current.next.next;
            current = current.next;
        }
        else{
            setContainer.remove(current.value);
            current = current.next; 
            //System.out.println(setContainer); Test
        }
    }
    return headNode;
}
public void printList(Node head){
    Node current = head;
    while(current.next != null){
        System.out.println(current.value);
        current = current.next;
    }
}}

This is the main method

public class mainTester {
    public static void main (String[] args){        
        Node node = new Node(10);
        node.next = new Node(20);
        node.next.next = new Node(12);
        node.next.next.next = new Node(11);
        node.next.next.next.next = new Node(10);
        node.next.next.next.next.next = new Node(20);
        node.next.next.next.next.next.next = new Node(30);
        node.next.next.next.next.next.next.next = new Node(30);
        node.printList(node);
        System.out.println("\nLets see how it goes");
        node.deleteNode(node);
        node.printList(node);
    }
}

The output after implementing deleteNode came as 10,20,12,11,20,30 which is not as expected. Please help correct this logical issue.

Answer 1

This is a more compact/efficient version of the logic that does not erase data

class Node{
    int value;
    Node next;

public Node(int value){
    this.value = value; 
    next = null;
}
public Node deleteNode(Node headNode){
    Node previous = null, current = headNode;
    HashSet<Integer> setContainer = new HashSet<Integer>();
    current = headNode; // reset current to the headNode

    while(current != null){
        if (!setContainer.contains(current.value)){
            setContainer.add(current.value);
            previous = current;
            current = current.next;
        }
        else{
            previous.next = current.next;
            current = current.next;
        }
    }
    return headNode;
}
public void printList(Node head){
    Node current = head;
    do{
        System.out.println(current.value);
        current = current.next;
    } while(current != null);
}}

The out put it generates with :

 Node node = new Node(10);
            node.next = new Node(20);
            node.next.next = new Node(12);
            node.next.next.next = new Node(11);
            node.next.next.next.next = new Node(10);
            node.next.next.next.next.next = new Node(20);
            node.next.next.next.next.next.next = new Node(30);
            node.next.next.next.next.next.next.next = new Node(30);
            node.next.next.next.next.next.next.next.next = new Node(20);
            node.next.next.next.next.next.next.next.next.next = new Node(30);
            node.next.next.next.next.next.next.next.next.next.next = new Node(40);
            node.printList(node);
            System.out.println("\nLets see how it goes");
            node.deleteNode(node);
            node.printList(node);

is

10
20
12
11
10
20
30
30
20
30
40

Lets see how it goes
10
20
12
11
30
40

Answer 2

private ListNode<Integer> removeDuplicate(ListNode<Integer> head) {
    Set<Integer> container = new HashSet<>();
    if (head == null) {
        return head;
    }
    ListNode<Integer> prev = head;
    ListNode<Integer> temp = head.getNext();
    while(temp != null) {
        if (container.contains(temp.getValue())) {
            prev.setNext(temp.getNext());
        } else {
            container.add(temp.getValue());
        }
    }
    return head;
}

public class ListNode<T extends Comparable<T>> {
private T value;
private ListNode<T> next;

public ListNode(T value) {
    this.value = value;
    next = null;
}

public T getValue() {
    return value;
}

public void setValue(T value) {
    this.value = value;
}

public ListNode<T> getNext() {
    return next;
}

public void setNext(ListNode<T> next) {
    this.next = next;
}
}

Answer 3

The error in your logic is after finding a duplicate, you are skipping to the next node after that without checking if that is a duplicate. You can fix this by changing

if(!setContainer.contains(node.next.value)) {

And just removing the second line

current = current.next

Also: You should be looping until current == null, not when setContainer is empty, as you could miss duplicates for instance if the same number was repeated twice at the end