Day 15：Remove Duplicates from linked list

这题开始之前先来介绍一下Linked list(连结串列)的资料结构。

Linked list(连结串列)使用node(节点)来记录、表示、储存资料(data)，并利用每个node中的pointer指向下一个node，来将多个node串起来。并以null 来代表Linked list的终点。

Node的结构如题目定义：

  function ListNode(val, next) {
      this.val = (val===undefined ? 0 : val)
      this.next = (next===undefined ? null : next)
  }

今天题目的目标是要把Linked list中node的数字重复者都移除掉，并回传移除後的结果，且题目有说这个Linked list是已经由小到大排序好的了，回传时也要是排序好的。

这题相较简单是因为题目给我们的Linked list是已经排序过的，今天如果没有排序过我们就需要用到之前提过的hashTable来储存已经拜访过的值，遇到重复的数再来调整pointer。

回到今天的题目。同理上面描述的这种方式当然可以套用在我们今天的题目，不过没有必要，因为我们的Linked list是已经排序过的，我们可以省掉额外储存的hashtable

以范例来说

Input: head = [1,1,2,3,3]
Output: [1,2,3]

目前Linked list的形状如下

1 → 1 → 2 → 3 → 3 → null

当我们今天一开始在１的时候

我们用一个temp来储存1的下一个数，也就是tmp = 1 (1.next = 1)

因为1 === 1

我们需要把第二个１拔掉

需要做以下的操作

current = head
// 把１的下下一个数（２）存到tmp
tmp = current.next.next
// 把１的下一个数换成tmp
current.next = tmp   

也就是说，我们只要一个loop，把这个Linked list走过，遇到next和现在一样，我们就仿造以上做法。如果有多个重复，我们可以利用while来实作，直到下个不同的node才去调整pointer

整体时间复杂度为：Ｏ(n)，空间复杂度为：Ｏ(1)

var deleteDuplicates = function (head) {
  let current = head;
  while (current !== null) {
    let nextDifferent = current.next;
    while (nextDifferent !== null && nextDifferent.val === current.val) {
      nextDifferent = nextDifferent.next;
    }
    current.next = nextDifferent;
    current = nextDifferent
  }
  return head;
};

看完上述的做法，不要忘记做做看如果Input Linked list没有sort的情况喔！

明日题目预告：挑战一下 Remove Nth Node From End of List（Medium）