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

题目描述

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

解题思路

有两个技巧：
1. 利用哈希表存储表中已经出现过的节点值，如果出现了就是重复元素
2. 开头设定一个指向头结点的new_head结点作为pre结点，方便后续便利时pre.next = node.next

解题代码

class Solution:
    def deleteDuplicates(self , head: ListNode):
        s = set()
        pre = ListNode(-1)
        new_head = pre
        pre.next = head
        node = head
        while node:
            if node.val in s:
                pre.next = node.next
                node = node.next
            else:
                s.add(node.val)
                pre = pre.next
                node = node.next
        return new_head.next