Removing duplicate element from a linked list- Java

Question

EDIT

I decided to use a HashSet instead as it has is O(N). However, I am still having an issue that it's not deleting all repeating numbers, 10 13 11 11 12 11 10 12 11. It returns : 10 13 11 12 10 11

static void removeDups(Node node) {
        HashSet<Integer> values = new HashSet<Integer>();
        Node previous = null;
        while(node != null) {
            if(values.contains(node.data)) 
                previous.next = node.next;
            else
                values.add(node.data);
                previous = node;

                node= node.next;

    }
    }

Irrelevant

I am trying to remove duplicate elements from a linked list but for some reason, It does not remove the last repeating element. For instance if the list is 10,11,12,11,12,9,11, It returns : 10,11,12,9,11.

     public static void removeDups1(Node head){
        if(head == head.next)
            head = head.next.next;
        Node fastptr =head;
        Node slowptr = head;
        while(slowptr.next != null && fastptr.next.next !=null) {
            if(slowptr.data == fastptr.data) {
                fastptr.next = fastptr.next.next;}

            slowptr = slowptr.next;
            fastptr = fastptr.next;

   }}

What the is that first if for? Why would the first element be pointing to itself? — markspace
– markspace, Commented Nov 1, 2017 at 2:30
i would expect a doubly nested while loop. your implementation doesn't seem close in the first place. — Jason Hu
– Jason Hu, Commented Nov 1, 2017 at 2:32
You should be comparing objects with .equals(). slowptr.data == fastptr.data should be slowptr.data.equals(fastptr.data). — teppic
– teppic, Commented Nov 1, 2017 at 2:33
Wrong in algorithm, for each element in node, you have to check all elements after it, you need double nested loop. — Nam Tran
– Nam Tran, Commented Nov 1, 2017 at 2:34
Sorry I think the algorithm without that error would still be flawed as you move slowptr in every step. — Joop Eggen
– Joop Eggen, Commented Nov 1, 2017 at 2:45

Sam · Accepted Answer · 2017-11-01 02:34:31Z

1

Checking fastptr.next.next == null prematurely exits your loop.

answered Nov 1, 2017 at 2:34

Sam

2,96919 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

inspired_learner Over a year ago

Thank you for your reply! I wasn't sure if that was what was happening

Aishwarya · Accepted Answer · 2017-11-01 02:47:21Z

0

Your algorithm is trying to find if there are any duplicates for each element from the current position to the next two positions in the linked list. But duplicates can occur anywhere in the linked list. Therefore, for each element, it should traverse through the linked list once again.

That would be a O(n^2) solution

A better approach would be to maintain a hash to keep track of already visited data.

This would be a O(n) solution.

answered Nov 1, 2017 at 2:47

Aishwarya

1106 bronze badges

Comments

inafalcao · Accepted Answer · 2017-11-01 02:54:19Z

0

I think, since at the beginning you are pointing both fastptr and slowptr to the same Node, and always end up pointing them to the same node at the end of the while, you're always comparing the same Nodes here, doing nothing valuable to the algorithm:

 if(slowptr.data == fastptr.data)

Anyways, the algorightm's logic seems all wrong.

Like others sayd, you should do two loops, one inside another: the first one to the slowptr, the second one to the fastptr

Try to implement based on this proposition:

For all Node (pointed by slowptr, first loop), for all subsequent nodes (second loop) do see if they are the same.

answered Nov 1, 2017 at 2:54

inafalcao

1,4522 gold badges13 silver badges26 bronze badges

Comments

bsaverino · Accepted Answer · 2017-11-01 03:15:32Z

0

I don't see real Java when I look to your code. But anyway as @Aishwarya said a better solution is to build a map or hash set for better performance. Using Java built-in functions it is even simpler. Just do:

LinkedList<Node> yourList = ...
LinkedList<Node> filteredList = new LinkedList<>(new HashSet<Node>(yourList));

To make this work properly you must make sure that Node equals(Object o) and hashCode()are correctly implemented.

Then your (generic) duplicate removal function might be:

public static void removeDups(LinkedList pList) {
    return new LinkedList(new HashSet(pList));   
    // indeed specifying <Node> is not really needed
}

edited Nov 1, 2017 at 3:15

answered Nov 1, 2017 at 3:08

bsaverino

1,28510 silver badges14 bronze badges

Collectives™ on Stack Overflow

Removing duplicate element from a linked list- Java

EDIT

Irrelevant

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

EDIT

Irrelevant

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related