content: package linkedlist;
  
  import java.util.HashSet;
  
  public class RemoveDuplicates {
  
  
      /*
       * Use hashset!!
       * Runtime Complexity:
       * Linear, O(n) - where 'n' is length of the linked list.
       *
       * Memory Complexity:
       * Linear, O(n) - to store nodes in hashset.
       * */
  
      public static class LinkedList {
  
          private Node head;
          public Node removeDuplicates(Node head) {
              Node currentNode = head;
  
              HashSet<Integer> hashSet = new HashSet<>();
              hashSet.add(currentNode.data);
  
              while (currentNode.next != null) {
                  if(hashSet.contains(currentNode.next.data)) {
                      currentNode.next = currentNode.next.next;
  
                  } else {
                      hashSet.add(currentNode.next.data);
                      currentNode = currentNode.next;
                  }
              }
              return head;
          }
  
          public void print(Node node) {
              while (node != null) {
                  System.out.print(node.data + " ");
                  node = node.next;
              }
          }
  
          public static class Node {
              private int data;
              private Node next;
  
              public Node(int data) {
                  this.data = data;
                  this.next = null;
              }
          }
      }
  
  
      public static void main(String [] args) {
  
          LinkedList linkedList = new LinkedList();
          linkedList.head = new LinkedList.Node(1);
          linkedList.head.next =  new LinkedList.Node(1);
          linkedList.head.next.next =  new LinkedList.Node(3);
          linkedList.head.next.next.next = new LinkedList.Node(2);
          linkedList.head.next.next.next.next = new LinkedList.Node(3);
          linkedList.head.next.next.next.next.next = new LinkedList.Node(1);
  
          linkedList.print(linkedList.head);
          linkedList.head = linkedList.removeDuplicates(linkedList.head);
          System.out.println("");
          linkedList.print(linkedList.head);
      }
  }
  