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/
