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

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.

Leave a Reply

Your email address will not be published. Required fields are marked *