Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
思路
用HashSet来解：对于每一个节点，如果在HashSet中存在，则删掉，若不存在，则加入HashSet。
Follow up
How would you solve this problem if a temporary buffer is not allowed?
用双指针分别指向pre和cur，双重循环，外循环循环整个链表，内循环每次从pre开始循环到链表尾部，遇到重复就删除。但是时间复杂度是O(n2)，用空间换时间
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
//用hashset来存已经存在的node，如果有重复，则remove
Set<Integer> set = new HashSet<Integer>();
//用前后两个node来比较，不要忘了第一个node需要加到hashset中
ListNode cur = head.next;
ListNode pre = head;
set.add(pre.val);
while (cur != null) {
if (!set.contains(cur.val)) {
set.add(cur.val);
cur = cur.next;
pre = pre.next;
} else {
cur = cur.next;
pre.next = cur;
}
}
return head;
}
}
