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();
}
}
Answer
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.