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帆阳，發(fā)現(xiàn)hashset添加元素叠纷，里面的順序跟原來不一樣了罗标。原來hashset的add是類似hashmap的O(1)的窃植。于是用了List趴腋，這樣contains操作復(fù)雜度又高了勘纯，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;
// }
事實上很簡單的挪圾，按照數(shù)據(jù)結(jié)構(gòu)書上那種就行了：
https://leetcode.com/problems/remove-duplicates-from-sorted-list/solution/
