BM16 删除有序链表中重复的元素-II

题目描述

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次。
例如：
输入：{1,2,2}
输出：{1}
输入：{}
输出：{}
链接：https://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024?tpId=295&tqId=663&ru=%2Fpractice%2Fc087914fae584da886a0091e877f2c79&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj

注意这个题和BM15 删除有序链表中重复的元素-I不同，那个题是遇到重复的时候保留一个，这个题是如果遇到重复那么一个都不保留

解题思路

类似之前的那个题，这个题有三个技巧：
1. 利用哈希表存储表中已经出现过的节点值，如果出现了就是重复元素
2. 开头设定一个指向头结点的new_head结点作为pre结点，方便后续便利时pre.next = node.next
3. 遍历两次，第一次记录将这个val出现的次数记录在dict里，在第二次遍历的时候删除重复的所有节点

解题代码

class Solution:
    def deleteDuplicates(self , head: ListNode):
        d = {}
        pre = ListNode(-1)
        new_head = pre
        pre.next = head
        node = head
        while node:
            if node.val in d.keys():
                d[node.val] += 1
            else:
                d[node.val] = 1
            node = node.next
        node = head
        while node:
            if d[node.val] > 1:
                pre.next = node.next
                node = node.next
            else:
                pre = pre.next
                node = node.next
        return new_head.next