Remove Duplicates From an Unsorted Linked List

Introduction

This blog will discuss the various approaches to solve the Remove duplicates from an unsorted linked list problem. Before jumping into the problem of removing duplicates from an unsorted linked list, let’s first understand a Linked list.

A Linked list is a kind of data structure in which the elements are connected using pointers, and each node has the address of the pointer of its next node.

In this Remove duplicates from an unsorted linked list problem, we need to return the head of the linked list after removing all the duplicates from the linked list.

You can refer to this link for more information on the linked list.

For Example:-

List :- 10 -> 15 -> 10 -> 5 -> 145 -> 15 -> 5 -> 11 -> 47 -> 10 -> 15 -> 75 

Output :- 10 -> 15 -> 5 -> 145 -> 11 -> 47 -> 75 

Let's move toward the approach section for this problem and know how to solve this in the Java language.

Recommended: Before stepping towards the solution try it by yourself on Coding Ninjas Studio.

Brute Force Approach

Brute Force Solution considers checking the complete linked list for the duplicate of each and every element using the nested loop and removing that duplicate element. 

Algorithm

Step 1. Create a function ‘getResult()’ that will accept one parameter, i.e., one head pointer of the linked list.

Step 2. Initialize two variables: ‘temp1’ will keep track of the element whose duplicates are being checked, and ‘temp2’ will keep track of the node that is being checked for the duplicate.

Step 3. Assign the value of ‘head’ to ‘temp1’ and assign the null value to ‘temp2’.

Step 4. Make an iteration using the ‘while’ loop, which will terminate if the value of ‘temp1’ or the ‘next’ pointer of ‘temp1’ is equal to null.

Step 5. Store value of ‘temp1’ in ‘temp2’.

Step 6. Make one nested iteration using the ‘while’ loop, which will terminate if the value of the ‘next’ pointer of ‘temp2’ is equal to null.

Step 7. Check if the value of both the ‘temp1’ and ‘temp2’ are equal or not, if they are equal, delete that node and increment the next pointer of ‘temp2’ to its next node’s next pointer and if not equal, then only increment it once.

Step 8. Increment the ‘next’ pointer of the ‘temp1’ node to its next node.

Java Solution

public class Solution 
{
    class Node
    {
        // Basic structure of the Node
        int data;
        Node next;
        // Constructor of this class ‘Node’
        Node(int x)
        {
            data = x;
            Next = null;
        }
    }
      
    static Node head;
    
    // Function to insert node in the linked list  
    static void push(Node headM , int x)
    {
        Node temp = new Node(x);
        temp.next = headM;
        headM = temp;
        head = headM;
    }

    Static void getResult(Node head) 
    {
            Node temp1 = null, temp2 = null;
            temp1 = head;
 
            /* Pick elements one by one */
            while (temp1 != null && temp1.next != null) 
            {
                   temp2 = temp1;
 
                   /* Comparing each element with the complete linked list
                   while (temp2.next != null) 
                   {
                          /* If duplicate of that node is present, then delete it */
                          if (temp1.data == temp2.next.data) 
                          {
                                 temp2.next = temp2.next.next;
                                 System.gc();
                          }
                          else 
                          {
                                 temp2 = temp2.next;
                          }
                   }
                   temp1 = temp1.next;
             }
    }

    static void printList(Node head)
    {
        int c = 0;
        while(head != null)
        {
            system.out.print(head.data + " ");
            head = head.next;
            c++;
        }
    }
    
    public static void main(String[] args) 
    {
        head = null; 
        push(head, 10);
        push(head, 15);
        push(head, 10);
        push(head, 5);
        push(head, 145);
        push(head, 15);
        push(head, 5);
        push(head, 11);
        push(head, 47);
        push(head, 10);
        push(head, 15);
        push(head, 75);
        System.out.println("Given Linked List :");
        printList(head);
        getResult(head);
        System.out.println("");
        System.out.println("Modified Linked List :");
        printList(head);
    }
}

Output :

Given Linked List:- 10 -> 15 -> 10 -> 5 -> 145 -> 15 -> 5 -> 11 -> 47 -> 10 -> 15 -> 75 

Modified Linked List:-  10 -> 15 -> 5 -> 145 -> 11 -> 47 -> 75 

Complexity Analysis

Time Complexity: O(N ^ 2)

Incall to ‘getResult()’, As we are using the nested loop to check for a duplicate of each element and then removing it, therefore, the overall time complexity is O(N ^ 2).

Space Complexity: O(1)

As we are using constant space, therefore, the overall space complexity will be O(1).

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm

Optimized Approach

To optimize this, Remove duplicates from an unsorted linked list problem; we’ll try to optimize the time complexity using the concept of hashing; in this approach, we will keep track of the node, if the node is already present in the hashmap, then it means it is the duplicate of that node, and we need to remove this duplicate node, and if that node is not present in that map, then this means that this is newly encountered node and we need to add this in the map.

Algorithm 

Step 1. Create a function ‘getResult()’ that will accept one parameter, i.e., one ‘head’ pointer of the linked list.. 

Step 2. Create an unordered Hashset ‘duplicate’ using ‘Collection’.

Step 3. Initialize two variables: ‘temp’ will keep track of the element whose duplicates are being checked, and ‘previous’ will keep track of the previous node of the ‘temp’.

Step 4. Assign the value of ‘head’ to ‘temp’ and assign the null value to ‘previous’.

Step 5. Make an iteration using the ‘while’ loop, which will terminate if the value of ‘temp’ is ‘null’.

Step 6. Assign the value of data of ‘temp’ to a variable ‘x’.

Step 7. Check if the value of ‘x’ is already in the ‘duplicate’ Hashset or not.

Step 8. If it is present in the map then we need to assign the value of the ‘next’ pointer of ‘temp’ to the ‘next’ pointer of ‘previous’, and if it is not present in the map, then add that value of ‘x’ in the map and make ‘previous’ equal to ‘temp’.

Step 9. Assign the value of the ‘next’ pointer of ‘temp’ to ‘temp’.

Java Solution

public class Solution 
{
    class Node
    {
        // Basic structure of the Node
        int data;
        Node next;
        // Constructor of this class ‘Node’
        Node(int x)
        {
            data = x;
            Next = null;
        }
    }
      
    static Node head;
    
    // Function to insert node in the linked list  
    static void push(Node headM , int x)
    {
        Node temp = new Node(x);
        temp.next = headM;
        headM = temp;
        head = headM;
    }
      
    static void getResult(Node head, int k)
    {
        HashSet<Integer> duplicate = new HashSet<>();
 
        node temp = head;
        node previous = null;


        // Traverse whole Linked List
        while (temp != null) 
        {
            int x = temp.val;


            // If the value of that node is already present in the map
            if (duplicate.contains(x)) 
            {
                previous.next = temp.next;
            }
            else 
            {
                duplicate.add(x);
                previous = temp;
            }
            temp = temp.next;
        }   
    }
     
    // Function to print Linked List 
    static void printList(Node head)
    {
        int c = 0;
        while(head != null)
        {
            system.out.print(head.data + " ");
            head = head.next;
            c++;
        }
    }
    
    public static void main(String[] args) 
    {

        head = null; 
        push(head, 10);
        push(head, 15);
        push(head, 45);
        push(head, 17);
        push(head, 145);
        push(head, 125);
        push(head, 5);
        push(head, 11);
        push(head, 47);
        push(head, 43);
        push(head, 1);
        push(head, 75);
    
        System.out.println("Given Linked List :");
    
        printList(head);
    
        getResult(head);
    
        System.out.println("");
    
        System.out.println("Modified Linked List :");
    
        printList(head);
    }

}

Output :

Given Linked List:- 10 -> 15 -> 10 -> 5 -> 145 -> 15 -> 5 -> 11 -> 47 -> 10 -> 15 -> 75 

Modified Linked List:-  10 -> 15 -> 5 -> 145 -> 11 -> 47 -> 75 

Complexity Analysis

Time Complexity: O(N)

Incall to ‘getResult()’, We are just traversing the whole linked list of length ‘N’ and checking for each node in the map, therefore, the average time complexity will be O(N), taking into consideration that accesses hash table is O(1). 

Space Complexity: O(N)

As we are using a hash table that will be of size ‘N’ in the worst case, therefore, the overall space complexity is O(N).

Check out this problem - Find Duplicate In Array

To understand it better and know proper code implementation, you should watch this video.

Frequently Asked Questions

What are the types of the Linked list?

A linked list is of three types:- Singly Linked List, Doubly Linked List, and Circular Linked List.

What is the difference between Singly Linked List and Doubly Linked List?

In Singly Linked List, each node has the address of the pointer to its next node, whereas, in Doubly Linked List, each node has the address of the pointers of its next node and its previous node. 

What is the Circular Linked List?

In Circular Linked List, the tail of the linked list points to the head of the same linked list.

Conclusion

In this article, we discussed the problem to remove duplicates from an unsorted linked list problem, discussed the various approaches to solving this problem programmatically, the time and space complexities, and how to optimize the approach by reducing the space complexity of the problem. 

Refer to these amazing articles based on LinkedList data structure→ How to Master Linked List, Applications of LinkedList, LinkedList Vs. Arrays, and many more!!!

Suggested problems based on LinkedList are Remove Duplicates from Sorted List, Add One to LinkedList, Cycle Detection in Singly LinkedList, and many more.

I hope that this blog has helped you enhance your knowledge regarding the above Data Structures and Algorithms problem and if you would like to learn more, check out our articles on the Coding Ninjas Studio. Enroll in our courses, refer to the test series and problems available, and look at the interview experiences and interview bundle for placement preparations for big tech companies like Amazon, Microsoft, Google, and many more. 

Do upvote our blogs if you find them helpful and engaging!