Remove Duplicates from an Unsorted Linked list

by

Objective: Write a program to remove the duplicates from an unsorted linked list

Example: 

Input Linked List : 1->2->2->4->3->3->2
Output : 1->2->4->3

Input: An unsorted linked list

Output: Linked list with no duplicates.

Approach:

  • Create a Hash Map
  • Take two pointers, prevNode and CurrNode.
  • PrevNode will point to the head of the linked list and currNode will point to the head.next.

  • Now navigate through the linked list.
  • Check every node data is present in the Hash Map.
  • if yes then delete that node using prevNode and currNode.
  • If No, then insert that node data into the Hash Map.
  • Return the head of the list

Time Complexity : O(n)
Space Complexity : O(n)

Follow Up: If suppose addition buffer is not allowed then we have option but to check every node data against every other node data and if find duplicates, delete that node.
Time Complexity : O(n^2)

Complete Code for the Hash Table method:


import java.util.HashMap;
public class RD {
public Node removeDup(Node head){
HashMap<Integer, Integer> ht = new HashMap<Integer, Integer>();
if(head==null){
return null;
}
Node currNode = head.next;
Node prevNode = head;
Node temp; //keeping it so that last node would be eligible for garbage collection
ht.put(head.data, 1);
while(currNode!=null){
int data = currNode.data;
if(ht.containsKey(data)){
prevNode.next = currNode.next;
temp= currNode;
currNode = currNode.next;
temp.next = null;
}else{
ht.put(data, 1);
prevNode = currNode;
currNode = currNode.next;
}
} return head;
}
public void display(Node head){
Node n=head;
while(n!=null){
System.out.print("->" + n.data);
n=n.next;
}
}
public static void main(String args[]){
Node n = new Node(2);
n.next = new Node(2);
n.next.next = new Node(2);
n.next.next.next = new Node(3);
n.next.next.next.next = new Node(4);
n.next.next.next.next.next = new Node(4);
n.next.next.next.next.next.next = new Node(2);
System.out.print("Original List : ");
RD rm = new RD();
rm.display(n);
System.out.print("\n Updated List: ");
Node x =rm.removeDup(n);
rm.display(x);
}
}
class Node{
int data;
Node next;
public Node(int data){
this.data = data;
next = null;
}
}

view raw

RemoveDuplicates.java

hosted with ❤ by GitHub

Output:

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

Related Posts: