Dinesh on Java

In this article, we will discuss another algorithm related to the singly linked list, how to remove duplicates from the unsorted singly linked list.  A singly linked list has several nodes, and each node in the list has the content and a pointer to the next node in the list. It does not store any pointer to the previous node.

Let’s have a look at the following more algorithms related the linked list:

• Find the nth node from the end of a singly linked list
• Find the middle element in a linked list
• How to Reverse linked list in Java
• Delete given node from a singly linked list
• A singly linked list is palindrome without extra space

Let’s discuss how to Remove Duplicates from the Unsorted Singly Linked list.

Remove Duplicates from the Unsorted Singly Linked list

In the following diagram, you can see the approach:

Here, we have an unsorted singly linked list, we have to write a program to remove the duplicates from an unsorted linked list.

Approach 1: We can use two loops

Step 1: In the first loop, hold each node data.

Step 2: In the second inner loop, we can match each node withhold data from the first loop.

Step 3: If node data is repeated, then delete that data.

This approach has O(n^2) time complexity. Let’s see the second approach with the O(n) time complexity as the following:

Approach 2: Using Hashmap

In this approach, we create a hashmap and using this hashmap we can remove duplicates from the unsorted singly Linked list.

Step 1: Create a HashMap
Step 2: Let’s consider two pointers such as prevNode and currNode.
Step 3: Let’s initialize these pointers as prevNode = head and currNode = head.next.
Step 4: Iterate this linked list and check every node data is present in the HashMap.
Step 5: If No, then insert that node data into the HashMap as the key.
Step 6: If Yes, then delete that node using prevNode and currNode.

As we can see this approach reduces the time complexity to O(n) but increases the space complexity by O(n). In my point of view, this approach much better than approach 1.

Let’s see the complete code:

package com.dineshonjava.algo;

/**
 * @author Dinesh.Rajput
 *
 */
public class Node {
	
    Node next;
    String data;
    
    public Node(String data) {
	super();
	this.data = data;
     }
}

The algorithm in java code as the below:

/**
 * 
 */
package com.dineshonjava.algo;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Dinesh.Rajput
 *
 */
public class RemoveDuplicateLinkedList {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		Node head = new Node("1");
		head.next = new Node("2");
		head.next.next = new Node("2");
		head.next.next.next = new Node("4");
		head.next.next.next.next = new Node("5");
		head.next.next.next.next.next = new Node("4");
		head.next.next.next.next.next.next = new Node("3");
        
		System.out.println("Original List : ");
        display(head);
        
        System.out.println("\nUpdated List: ");
        Node update = deDup(head);
        display(update);
	}
	
	private static Node deDup(Node head) {
		
		if(head == null || head.next == null) {
			return head;
		}
		
		Node prevNode = head;
		Node currNode = head.next;
		Node temp = null;
		
		Map<String, Integer> map = new HashMap<>();
		
		map.put(prevNode.data, 1);
		
		while(currNode != null) {
		
			if(map.containsKey(currNode.data)) {
				temp = currNode;
				prevNode.next = currNode.next;
				currNode = currNode.next;
				temp = null;
			}else {
				map.put(currNode.data, 1);
				prevNode = currNode;
				currNode = currNode.next;
			}
			
		}
		return head;
	}

	private static void display(Node head){
        Node n=head;
        while(n!=null){
            System.out.print("->" + n.data);
            n=n.next;
        }
	}

}

Run above program, you will get the following output:

Original List : 
->1->2->2->4->5->4->3
Updated List: 
->1->2->4->5->3

In this example, we have written a program to remove duplicates from the unsorted singly linked list

Hope, you have understood this solution. Please share other solutions if you have. :).

Happy learning with us!!!.