Remove Duplicates From an Unsorted Linked List

lcpy gen -n 1836   # by problem number
lcpy gen -s remove_duplicates_from_an_unsorted_linked_list   # by problem name

Input: head = [1,2,3,2]
Output: [1,3]
Explanation: 2 appears twice in the linked list, so all 2's should be deleted. After deleting all 2's, we are left with [1,3].

Input: head = [2,1,1,2]
Output: []
Explanation: 2 and 1 both appear twice. All the elements should be deleted.

Input: head = [3,2,2,1,3,2,4]
Output: [1,4]
Explanation: 3 appears twice and 2 appears three times. After deleting all 3's and 2's, we are left with [1,4].

from leetcode_py import ListNode


class Solution:
    # Time: O(n)
    # Space: O(n)
    def delete_duplicates_unsorted(self, head: ListNode[int] | None) -> ListNode[int] | None:
        seen: set[int] = set()
        dupes: set[int] = set()
        cur = head
        while cur is not None:
            if cur.val in seen:
                dupes.add(cur.val)
            seen.add(cur.val)
            cur = cur.next

        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        cur = head
        while cur is not None:
            nxt = cur.next
            if cur.val in dupes:
                prev.next = nxt
            else:
                prev = cur
            cur = nxt
        return dummy.next