• Register
Welcome to Developerhelpway Q&A, where you can ask questions and receive answers from other members of the community.

Remove duplicates from sorted linked list java

0 votes
37 views
Remove duplicates from sorted linked list java.
List :- [10,10,10, 15, 20, 20, 20, 25, 30, 30]
Output:- [10 15 20 25 30]
asked Jan 19 in Data Structure And Algorithm by Abhishek Kumar

1 Answer

0 votes
With the help of following example, we see two ways to remove duplicates from sorted linked list. I would like to prefer you to use removeDuplicatesOptimized() function for bette performance.

package com.ds.linkedlist;

public class RemoveDuplicatesFromSortedLinkeddList {

    Node head;
   
    public static void main(String[] args) {
        RemoveDuplicatesFromSortedLinkeddList remove = new RemoveDuplicatesFromSortedLinkeddList();
        remove.insert(10);
        remove.insert(10);
        remove.insert(10);
        remove.insert(15);
        remove.insert(20);
        remove.insert(20);
        remove.insert(20);
        remove.insert(25);
        remove.insert(30);
        remove.insert(30);
       
        System.out.println("Origianal List: ");
        remove.print();
        System.out.println("\nAfter removing duplicates List: ");
//        remove.removeDuplicates(remove.head);
        remove.removeDuplicatesOptimized(remove.head);
        remove.print();
    }
   
    //Time Complexity O(n) and Space Complexity O()
    public void removeDuplicates(Node head){
        Node current = head, removed = null, old = null;
        while(current != null){
            if(old != null && old.data != current.data){
                //add in final removed duplicates node
                Node node = new Node(current.data);
                if(removed == null){
                    removed = old;
                    removed.next = node;
                }else{
                    Node temp = removed;
                    while(temp.next != null)
                        temp = temp.next;
                    temp.next = node;
                }
            }
            old = current;
            current = current.next;
        }
        this.head = removed;
    }
   
    //Time Complexity O(n) and Space Complexity O(1)
    public void removeDuplicatesOptimized(Node head){
        Node current = head, next_next;
        while(current.next != null){
            if(current.data == current.next.data){
                next_next = current.next.next;
                current.next = null;
                current.next = next_next;
            }else{
                current = current.next;
            }
        }
    }
   
    public void insert(int data){
        Node newNode = new Node(data);
        if(head == null){
            head = newNode;
        }else{
            Node curr = head;
            while(curr.next != null){
                curr = curr.next;
            }
            curr.next = newNode;
        }
    }
   
    public void print(){
        if(head==null)
            return;
        Node curr = head;
        while(curr != null){
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
    }
   
    private class Node{
        int data;
        Node next;
        Node(int data){
            this.data = data;
        }
    }
}

Output: -
Origianal List:
10 10 10 15 20 20 20 25 30 30
After removing duplicates List:
10 15 20 25 30
answered Jan 19 by ranju_12 (1,740 points)
...