7. Remove duplicates from an unsorted linked list

7. Remove duplicates from an unsorted linked list

Problem link :- click here

package Linked_List;

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

public class LinkedList__7
{

	static void removeDuplicates(LinkedList list)
	{
		//This is unsorted linked list we will use hash map to solve this
		Map<Integer, Integer> map = new HashMap<>();
		
		Node temp = list.head;
		for(temp=list.head; temp!=null; temp=temp.next)
		{
			if( !map.containsKey(temp.data) )
				map.put(temp.data, 1);
			else
				map.put(  temp.data, map.get(temp.data)+1  );
		}
		
		//we will now iterate through the linked list if we come across a duplicate
		//node then we will remove that node
		Node prev, cur;
		prev = list.head;
		cur = prev.next;
		for(cur = prev.next; cur!=null; cur=cur.next)
		{
			if(map.get(cur.data) > 1)
			{
				Node next = cur.next;
				prev.next = next;
				//Here we should not update the previous the node 
				//but we must update the value in the hash map
				map.put(   cur.data, map.get(cur.data) - 1    );
			}
			else
				prev = prev.next;
		}
	}
	
	public static void main(String[] args)
	{
		LinkedList list = new LinkedList();
		list.push(4);
		list.push(2);
		list.push(3);
		list.push(1);
		list.push(3);
		list.push(2);
		
		System.out.println("Linked list before removing dulpicates : ");
		printList(list);
		
		removeDuplicates(list);
		System.out.println("Linked list after removing dulpicates : ");
		printList(list);
	}

	static void printList(LinkedList list)
	{
		for(Node temp=list.head; temp!=null; temp=temp.next)
			System.out.print(temp.data + "-> ");
		System.out.println("null");
	}
}

Time complexity :- O(n)
Space complexity :- O(n)