Leetcode 1836 Remove Duplicates From an Unsorted Linked List

Problem statement

https://leetcode.com/problems/remove-duplicates-from-an-unsorted-linked-list/

Solution

The idea is to traverse linked list two times:

1. First time to calculate frequencies.
2. Second time to collect only nodes with frequecy 1.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def deleteDuplicatesUnsorted(self, head):
        curr = head
        cnt = Counter()
        
        while curr:
            cnt[curr.val] += 1
            curr = curr.next
            
        curr = head
        last = head2 = ListNode(0)
        while curr:
            if cnt[curr.val] == 1:
                last.next = ListNode(curr.val)
                last = last.next
            curr = curr.next
        
        return head2.next