Remove Duplicated from Sorted List II

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Approach1: Two pass - Dictionary

My first thought upon reading this problem is to use a dictionary to solve it. We would first do a first pass through which the dictionary would store the frequency of each value of the Linked List. Having stored the frequencies, we execute a second pass so we can now delete each values for which their count in the dictionary is greater than 1 hence a duplicate.

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        dummy = curr = ListNode(None)
        dummy.next = head
        curr = curr.next 
        count = {}
        
        while curr:
            count[curr.val] = count.get(curr.val, 0) + 1
            curr = curr.next
        
        curr = dummy
        
        while curr.next:
            if count[curr.next.val] > 1:
                curr.next = curr.next.next
            else:
                curr = curr.next
        
        return dummy.next 

Time: O(n) Space: O(n)

Approach2: One Pass (optimal)

Although the above code works perfectly, we know that considering that the Linked List is sorted, we should be able to avoid utilizing any additional additional data structures that are ramping up our space complexity. After profound reflection (not really, got the hint :) ), we should be able to get O(1) space by applying this fundamental concept.

Iterate through the Linked List with a curr pointer pointer followed by a prev pointer. When the curr pointer encounters an element that is equal to it's current value. Curr pointer runs until it's next element does not equal to it's current value. Once that occurs, prev pointer's -> next then prints at curr's -> next thereby deleting all elements that were duplicates. As often with Linked List's, we return dummy->next.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head 
        
        dummy = prev = curr = ListNode(None)
        dummy.next = head 
        
        while curr and curr.next:
            if curr.val == curr.next.val:
                while curr.next and curr.val == curr.next.val:
                    curr = curr.next
                prev.next = curr.next
                curr = prev.next
            else:
                prev = curr
                curr = curr.next 
        
        return dummy.next