CODEWITHSUNDEEP
javadatabasealgorithm
sssszzzzzzssszzz
sssszzzzzzssszzz

Reputation: 163

Why can't I remove duplicates from linked list?

     /*
DEFINITIONS

 public class ListNode {
        int val;
        ListNode next;
        public ListNode(int x){
            val = x;
            next = null;
        }

    }


    public class LinkedList {
        ListNode head;
    }
    */


    public void removeDups(){
        ListNode head = this.head;
        if(head == null) return;

        HashSet<ListNode> set = new HashSet<>();
        set.add(head);
        while(head.next != null){
            if(set.contains(head.next)){
                head.next = head.next.next;
            } else{
                set.add(head.next);
                head = head.next;
            }
        }
    }

I am supposed to remove duplicates from an unsorted list, but it isn't working in Java.

1->2->4->9->9->4 should return 1->2->4->9 but it still returns 1->2->4->9->9->4

What is the issue? I am clearly inserting all nodes into a hashset and checking if it contains, but not sure what is happening?

Upvotes: 1

Views: 157

Answers (3)

Shadov
Shadov

Reputation: 5591

You are trying to check if set contains the ListNode, but you didn't override the equals method in ListNode class. Try overriding it, or add values to set, not the whole nodes, it will work since values are simple integers.

You should also override the hashCode method, as you should always do when overriding equals - thanks Andy Turner

Upvotes: 1

Andy Turner
Andy Turner

Reputation: 140494

Just to add to v78's answer, which correctly describes the reason why it doesn't currently work:

Alternatively, you could implement equals and hashCode in the ListNode class, which would allow the nodes to be considered equal if they have the same val:

int hashCode() { return val; }

boolean equals(Object other) {
  if (other == this) return true;
  return (other instanceof ListNode)
      && val == ((ListNode) other).val;
}

Upvotes: 1

v78
v78

Reputation: 2933

You are removing duplicate nodes, not duplicate valued nodes in the code you posted.

 /*
DEFINITIONS

public class ListNode {
    int val;
    ListNode next;
    public ListNode(int x){
        val = x;
        next = null;
    }

}


public class LinkedList {
    ListNode head;
}
*/


public void removeDups(){
    ListNode head = this.head;
    if(head == null) return;

    HashSet<Integer> set = new HashSet<Integer>();
    set.add(head.val);
    while(head.next != null){
        if(set.contains(head.next.val)){
            head.next = head.next.next;
        } else{
            set.add(head.next.val);
            head = head.next;
        }
    }
}

Upvotes: 6

Related Questions