Remove duplicates from a sorted LinkedList in Java

Hi coders! I am back with a problem that is related to many people’s favourite data structure Linked List. The problem is to remove duplicate nodes from a sorted LinkedList in Java.

Let us consider an example :

We have given a sorted linked list 10->20->20->30->30->40, we have to remove duplicates from this list and the result after removal of duplicates will be like 10->20->30->40Hence to solve this problem there are various approaches like a naive approach is to use two loops and check for each element if there is a duplicate remove that element, but this approach would be costly as it will have the time complexity of O(n^2).

So I am suggesting an approach that will use the concept of recursion.

In this approach, there will be a pointer Node that will traverse the linked list one by one, so the function will be called with the argument  current Node(Node that is referenced by the pointer Node) and its Next adjacent Node if both the Node values are not equal. If found equal then update the Next Node till the different value is not found and then make the current node connection with the Node referenced by Next Node.

Java program to remove duplicates from a sorted LinkedList

public class Remove {
 public  Node head;
 public Node tail;


   public class Node {       /* create Node */
  public int data;
   public Node next;
  public Node(int d ) {
    this.data = d;
    this.next = null;
  }

}
          public void push(int newdata) {            /* function to add node at front */
    Node newnode = new Node(newdata);
    newnode.next = head;
    head = newnode;
  }


 public void append(int newdata) {    /* function that add node at last of list*/
    Node newnode = new Node(newdata);
    if (head == null) {
      head = newnode;
      
      return;
    }
    newnode.next = null;
    Node temp = head;
    while (temp.next != null) {
      temp = temp.next;
    }
    temp.next = newnode;
    tail = newnode;
    return;
  }
public static void removeDuplicacy(Node start, Node Next) {  /* function to remove duplicates */

  if (start == null && start.next == null) {
    return ;
  }
  if(start.data != Next.data) {
    removeDuplicacy(start.next, Next.next);
  }
  while(Next != null ) {
  
    if(Next.data != start.data) {
      start.next = null;
      start.next = Next;
      start = Next;
    
    }
    Next = Next.next;
  }
  
}

  public void print(Node head) {  /* function to print the list */
    Node traverse = head;
    while (traverse != null) {
      System.out.print(traverse.data + " ");
      traverse = traverse.next;
    }
  }
  public static void main(String[] args) {
    Remove li = new Remove();
    li.push(20);
    li.push(20);
    li.push(10);
    li.append(30);
    li.append(30);
    li.append(40);
    System.out.println("Original list");
      
    li.print(li.head);
    System.out.println(); 
    removeDuplicacy(li.head, li.head.next);
    System.out.println("List after removing duplicates");
            
    li.print(li.head);
  }



}
// Code is provided by Anubhav Srivastava
Output 

Original list

10 20 20 30 30 40

List after removing duplicates

10 20 30 40

Hence the solution is quite efficient.

Hope you like the solution.

Leave a Reply

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