leetcode每日一题之删除排序链表中的重复元素
题目链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/submissions/
题目描述：
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
返回同样按升序排列的结果链表。
例子1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
例子2：
输入：head = [1,1,1,2,3]
输出：[2,3]
解法1：
这里参考大佬的一个解法：
考虑到一些边界条件，比如1->1->1->2这种情况，需要把开头的几个1给去掉，我们增加一个哑结点，方便边界处理。
初始的两个指针如下:
- 将a指针指向哑结点
- 将b指针指向head(哑结点的下一个节点)
如果a指向的值不等于b指向的值，则两个指针都前进一位
否则，就单独移动b，b不断往前走，直到a指向的值不等于b指向的值。
注意，这里不是直接比较a.val==b.val，这么比较不对，因为初始的时候，a指向的是哑结点，所以比较逻辑应该是这样：
a.next.val == b.next.val
当两个指针指向的值相等时，b不断往前移动，这里是通过一个while循环判断的，因为要过滤掉1->2->2->2->3重复的2。
下面是程序走的过程
代码：
//输入：head = [1,2,3,3,4,4,5]
//输出：[1,2,5]
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
//定义一个呀节点指向头节点，因为头节点也有可能被删除
ListNode dummy = new ListNode(-1);
dummy.next = head;
//a节点指向呀节点
ListNode a = dummy;
//b节点指向头节点
ListNode b = head;
while (b != null && b.next != null) {
//初始化的时候a是指向呀节点，因此比较的逻辑应该是a的下一个节点的值和b的下一个节点的值
if (a.next.val != b.next.val) {
a = a.next;
b = b.next;
} else {
//如果，a，b指向的节点值相等，则不断的移动b，直到a，b指向的值相等
while (b != null && b.next != null && a.next.val == b.next.val) {
//如果值相等，b向后移动看是否还相等
b = b.next;
}
a.next = b.next;
b = b.next;
}
}
return dummy.next;
}
对于链表这类题，可以自己画一下走的过程，防止被绕晕
解法2
：
具体做法如下:
- 遍历链表，将每个节点的值放到哈希表中，哈希表的key就是节点的值，value是这个值出现的频率
- 遍历哈希表，将所有频率==1的key放到集合中
- 对集合进行排序
- 遍历集合，然后不断创建新的链表节点
当然这里可以优化一下，比如使用LinkedHashMap（LinkedHashMap 能记录下放入元素的顺序，并保证取出的时候顺序保持不变）或者OrderedDict这样的数据结构，可以省去排序环节。
LinkedHashMap的有序性：https://blog.csdn.net/topc2000/article/details/79798513
代码实现:
//解法2
public ListNode deleteDuplicates2(ListNode head) {
if(head==null || head.next==null) {
return head;
}
//用哈希表记录每个节点值的出现频率
HashMap<Integer,Integer> cache = new HashMap<Integer,Integer>();
ArrayList<Integer> arr = new ArrayList<Integer>();
ListNode p = head;
while(p!=null) {
int val = p.val;
if(cache.containsKey(val)) {
cache.put(val,cache.get(val)+1);
} else {
cache.put(val,1);
}
p = p.next;
}
//将所有只出现一次的值放到arr中，之后再对这个arr排序
for(Integer k : cache.keySet()) {
if(cache.get(k)==1) {
arr.add(k);
}
}
Collections.sort(arr);
ListNode dummy = new ListNode(-1);
p = dummy;
//创建长度为arr.length长度的链表，依次将arr中的值赋给每个链表节点
for(Integer i : arr) {
ListNode tmp = new ListNode(i);
p.next = tmp;
p = p.next;
}
return dummy.next;
}
**参考链接：**https://mp.weixin.qq.com/s/UJdtPllv5erPIZvMDQAuIg
注：大家也可以直接搜索微信公众号大话算法，基本都带有配图，写的很不错，我不会的一般都是参考这位大佬。