LeetCode----Remove Duplicates from Sorted List II

Remove Duplicates from Sorted List II
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 .
分析:
チェーンテーブルの重複するすべての要素を削除します.
コレクションを使用して、重複したすべての要素を記録し、チェーンテーブルを再度巡回し、重複したコレクション内のノードに新しいチェーンテーブルを追加しません.時間複雑度はO(n),空間もO(n)であった.
もちろん、繰り返しではない要素を毎回探し出し、新しいチェーンテーブルを追加することで、空間はO(1)を満たすが、時間はO(n^2)である.
コード:

class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        p = head
        v = set()  # record all the values
        d = set()  # record only the duplicate values
        while p:
            if p.val not in v:
                v.add(p.val)
            else:
                d.add(p.val)
            p = p.next
        p = head
        r = q = ListNode(-1)
        while p:
            if p.val not in d:
                q.next = p
                q = q.next
            p = p.next
            q.next = None
        return r.next