removeDuplicates.md

Prompt

Given an unsorted Linked List (singly linked), write a function that removes all additional duplicate values in the list.

---

---

Given

A prebuilt singly linked list will be written for us already, just as follows:

class LinkedList {
  constructor(head) {
    this.head = head || null;
  }
  
  addToHead(value) {
    let newNode = new ListNode(value);
    let oldHead = this.head;
    if (oldHead) newNode.next = oldHead;
    this.head = newNode;
    return this;
  }
}

class ListNode {
  constructor(value, next) {
    this.value = value;
    this.next = next || null;
  }
}

Also to preface we do want to mutate our original list.

---

Examples

let list1 = new LinkedList();
list1.addToHead(5).addToHead(3).addToHead(8);

let list2 = new LinkedList();
list2.addToHead("b").addToHead("a").addToHead("a").addToHead("c");

let list3 = new LinkedList();
list3.addToHead(3).addToHead(4).addToHead(5).addToHead(3)

let list4 = new LinkedList();
list4..addToHead(1).addToHead(1);

removeDuplicates(list1); // return 8 -> 3 -> 5
removeDuplicates(list2); // return "c" -> "a" -> "b"
removeDuplicates(list3); // return 3 -> 5 -> 4
removeDuplicates(list4); // return 1

---

---

---

First Solution (time optimized)

function removeDuplicates(list) {
  let pointer = list.head;
  if (!pointer) return null; // no list

  let listValues = getValues(list); // store the list values in an object for reference

  while(pointer) {
    if (pointer.next) {
      if (listValues[pointer.next.value] > 1) { // find a duplicate node 
        pointer.next = pointer.next.next; // remove the node by removing the reference to it
      }
      else {
        pointer = pointer.next;
      }
    }
    else {
      pointer = pointer.next;
    }
  }
  return list;
}

function getValues(list) {
  let values = {};
  let pointer = list.head;

  while(pointer) {
    if (values[pointer.value]) { // any duplicate will have a value in this object greater than 1;
      values[pointer.value] += 1;
    }
    else {
      values[pointer.value] = 1;
    }
    pointer = pointer.next;
  }
  return values;
}

This solution will run through two iterations of our linked list. This will come out to have a runtime of O(n), where n is equal to the number of nodes in our list. This apporach first checks each node in our list once, and stores the values in an object for reference. Our function then goes through our list again and checks to see if any duplicates exist, and proceeds to remove them. To do this with faster time, space allocation is neccessary and our space complexity is also O(n), where n is the number of nodes in our list.

Second Solution (memory optimized)

function removeDuplicates(list) {
  let pointer = list.head;

  while(pointer && pointer.next) {
    let runner = pointer;
    while (runner.next) {
      if (pointer.value === runner.next.value) {
        runner.next = runner.next.next; // remove the duplicate node by removing the reference to it
      }
      else {
        runner = runner.next; // run through every other node in the list
      }
    }
    pointer = pointer.next; // move to the next node to cehck for duplicates
  }

  return list;
}

This approach will occur in O(1) space complexity, as there are only two additional references being made, our pointer and runner, no matter the size of our input. In terms of time complexity, we have to loop our list for every node in our list, coming out to roughly be O(n^2) time. Either approach is valid, as they both compensate time/space complexity to optimize the other. These trade-offs occur frequently in algorithms, and it's good to note that they exist.