CODEWITHSUNDEEP
javalinked-list
Jae Kim
Jae Kim

Reputation: 675

Deleting duplicates a linked lists Java

I am trying to implement a method that deletes all the duplicates from a linked list. I've managed to take care of the tail. In other words, if the tail's data was a duplicate, the program wouldn't throw an exception error. Now, I'm trying to take care of the head such that if the head's data is a duplicate, I want to set the head = head.next so that the duplicate is no longer in the linked list. However my method deleteDuplicates does not handle the head. Anybody have suggestions to fix this problem?

class Node {
        private Node next = null; 
        private int data; 

        public Node(int d) {
            data = d; 
        }

        void appendToTail(int d) {
            Node end = new Node(d); 
            Node n = this; 

            while(n.next != null) {
                n = n.next; 
            }
            n.next = end; 
        }

        void print() {
            Node n = this; 
            while(n != null) {
                System.out.println(n.data); 
                n = n.next; 
            }
        }

        Node deleteDuplicates(Node head, int d) {
            Node n = head;
            if(n.data == d) {
                head = head.next; 
                n = n.next; 
            }
            while(n != null) {
                if(n.next.data == d) {
                    if(n.next == null && n.next.data == d) {
                        return head;
                    }
                    n.next = n.next.next;
                }
                n = n.next; 
            }
            return head; 
        }

        public static void main(String [] args) {
            Node x = new Node(9); 
            x.appendToTail(5);
            x.appendToTail(9);
            x.appendToTail(6);
            x.appendToTail(9);  
            x.appendToTail(7);
            x.appendToTail(9);  
            x.appendToTail(8); 
            x.appendToTail(9); 
            x.deleteDuplicates(x, 9); 
            x.print(); 
        }   
    }

Upvotes: 0

Views: 110

Answers (5)

janos
janos

Reputation: 124724

You want to keep removing the head as long as it matches the value. So replace the if with a while:

Node n = head;
while (n != null && n.data == d) {
    n = n.next; 
}
head = n;

You have other problems too. This line for example will raise a null pointer exception when n.next is null:

if(n.next == null && n.next.data == d) {

Fixing your while loop:

while (n.next != null) {
    if (n.next.data == d) {
        n.next = n.next.next;
    } else {
        n = n.next;
    }
}

Lastly, the method name you chose is very misleading. "deleteDuplicates" suggests deleting all duplicates, for example:

from: 9->5->6->9->7->9->8->9  
  to: 9->5->6->7->8

It would make sense to call this method just delete.

Putting it together

With the above corrections applied, the method becomes:

Node delete(Node head, int d) {
    Node n = head;

    // skip consecutive d values at head
    while (n != null && n.data == d) {
        n = n.next; 
    }
    head = n;

    // skip d values
    while (n.next != null) {
        if (n.next.data == d) {
            n.next = n.next.next;
        } else {
            n = n.next;
        }
    }

    return head;
}

Upvotes: 1

StackFlowed
StackFlowed

Reputation: 6816

Verified by running code. You code should look like this :

x.deleteDuplicates(x, 9).print();

Then the delete method should be : 

Node deleteDuplicates(Node head, int d) {
    Node nextNode=head;
    if(head.data == d) {
        if(head.next==null) {
            return null;
        }
         return deleteDuplicates(head.next, d);
    }
    Node previous=head;
    while(nextNode.next != null) {
        nextNode=nextNode.next;
        if(nextNode.data == d) {
            previous.next=nextNode.next;
        }
        previous=nextNode;
    }
    return head;
}

Output : 

5
6
7
8

In the you check if the head node needs to be deleted you make the next node as head node. You also check if last node is to be deleted then you make the previous nodes next as null.

Upvotes: 0

Aaron
Aaron

Reputation: 24812

If all you need is a container of unique objects, the best way to go is to have these objects implement the .equals() and .hashCode() methods so you can use a Set to handle the uniqueness logic.

Equality can be easily implemented as an addition of all the class' fields equality, and hashCode from a hash of the concatenation of all the class' fields hashCodes.

If you need them to be linked for some reason, LinkedHashSet is there for you.

Example with Integers :

LinkedHashSet<Integer> myCollection = new LinkedHashSet<Integer>();
myCollection.add(5);
myCollection.add(3);
myCollection.add(2);
myCollection.add(5);
myCollection.add(2);
System.out.println(myCollection);
// prints [5, 3, 2]

An example with a custom class can be found here.

Upvotes: 0

alampada
alampada

Reputation: 2409

Something like (untested code):

The idea is that for each element, traverse the rest of the list and remove and duplicates of the current element

public void deleteDupes(Node head) {
  if (head == null || head.next == null) {
    return;
  }
  Node current = head;
  while (current != null) {
    Node runner = head;
    while (runner.next != null) {
      if (runner.next.val == current.val) {
        runner.next = runner.next.next;
      }
      else {
        runner = runner.next;
      }
    }
    current = current.next;
  }
}

Upvotes: 0

Dinesh
Dinesh

Reputation: 983

The problem in your code is that you haven't reassigned your head after deletion. If you modify it as follows, I think your head deletion problem will be solved.

x = x.deleteDuplicates(x, 9);

Needless to say, there are other efficient methods like hashing which can be used to bring down the time complexity of your code.

Upvotes: 1

Related Questions