RemoveDuplicatesSLinkedList.js

/* Author - Aman Meghrajani - amanmeghrajaniatgmaildotcom */

/* Remove Duplicates in a Singly Linked List
   Input  - head Node of SinglyLinkedList
   Output - void
   Notes  - We will cache all elements that occur once and remove them if they occur again

*/

function removeDuplicates (head) {
  if(!head) { return; }
  
  /* JS uses hash table underneath, O(1) mutation complexity */
  var cache = new Set(); 
  var node, next, prev;
  
  /* Process head Node in advance */
  cache.add(head.value); 
  prev = head;           
  node = head.next;
  
  while(node){
    
    if(cache.has(node.value)) {
      /* In Cache, link previous element to next element */
      /* Previous stays same */
      /* Since we will remove current node and process next node */
      prev.next = node.next;
    } else {
      /* Cache Miss, Cache element and continue to next node */
      cache.add(node.value)
      prev = node
    }
      node = node.next;
    
  }
  
}


/* Print a Singly Linked List
   Input  - head Node of SinglyLinkedList 
   Output - void
*/


function printList (head) {
  if(!head) { 
    console.log("no list provided");
    return;
  } 
  
  let node   = head;
  let buffer = "" + node.value;
  
  while(node.next) {
    buffer += " -> " + node.next.value
    node = node.next
  }
  
  console.log(buffer);
}


/* Consturctor - Node for SinglyLinkedList 
   Input       - Optional Int, Optional next Node
   Output      - new Node   
*/

function Node(value, next) {
  this.value = parseInt(value) != "NaN" ? value : null
  this.next  = next || null
}

/* Constructor - SinglyLinkedList 
   Input       - Optional head Node
*/

function SinglyLinkedList (node) {
  this.head = node || null
  this.removeDuplicates = () => removeDuplicates(this.head)
  this.printList        = () => printList(this.head)
}



/* Test */
console.log("Singly Linked List Test");

let list                           = new SinglyLinkedList(new Node(5));
list.head.next                     = new Node(2);
list.head.next.next                = new Node(3);
list.head.next.next.next           = new Node(2); //rem
list.head.next.next.next.next      = new Node(5); //rem consecutive
list.head.next.next.next.next.next = new Node(6, new Node(2)); //rem last



/* Before and After Test */
list.printList()
list.removeDuplicates()
list.printList()