83. Remove Duplicates from Sorte

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

这题我用O(1)space没做出来，就用了额外空间，一开始用的是hashset，发现hashset添加元素，里面的顺序跟原来不一样了。原来hashset的add是类似hashmap的O(1)的。于是用了List，这样contains操作复杂度又高了，O(n2)。

    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        List<Integer> set = new ArrayList<>();
        while (head != null) {
            if (!set.contains(head.val))
                set.add(head.val);
            head = head.next;
        }
        ListNode node = new ListNode(-1);
        ListNode fakeHead = node;
        for (Integer i : set) {
            node.next = new ListNode(i);
            node = node.next;
        }
        return fakeHead.next;
    }

下面是我想用fakeHead来做的，没做出来：

//  public ListNode deleteDuplicates(ListNode head) {
//      //这样可以吗，如果可以为什么要记录fakeHead.next = head
//      ListNode fakeHead = new ListNode(-1);
//      while (head != null) {
//          head.next = nextNonDuplicateNode(head);
//          head = head.next;
//      }
//      return fakeHead;
//  }
//
//  private ListNode nextNonDuplicateNode(ListNode node) {
//      if (node.next == null)
//          return null;
//      while (node.val == node.next.val) {
//          node = node.next;
//      }
//      return node.next;
//  }

事实上很简单的，按照数据结构书上那种就行了：
https://leetcode.com/problems/remove-duplicates-from-sorted-list/solution/