Problem of The Day: Remove Duplicates from Sorted List II

Problem Statement

My notes:

O(n) Space Approach

Intuition

My initial thought is to iterate through the list, keeping track of the frequency of each node’s value. This frequency information can then be used to identify and delete duplicate nodes.

Approach

• Initialize a dummy node to simplify handling edge cases.
• Iterate through the list and count the frequency of each node’s value using a defaultdict.
• Iterate through the list again. If a node’s value has a frequency greater than 1, skip it and update the pointers to remove it from the list.
• Return the modified list.

Complexity

• Time complexity: O(n), where n is the number of nodes in the linked list. We process each node twice, once for counting frequencies and once for removing duplicates.

• Space complexity: O(n), as we use a defaultdict to store the frequency of each node’s value.

Code

# 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: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(-101, head)
        prev = dummy
        freq = defaultdict(int)
        curr = head
        while curr:
            freq[curr.val] += 1
            curr = curr.next

        curr = head
        while curr:
            if freq[curr.val] > 1:
                curr = curr.next
                prev.next = None
            else:
                prev.next = curr
                prev = curr
                curr = curr.next

        return dummy.next

Editorial Solution

Approach 1: Sentinel Head + Predecessor

O(1) space approach

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        # sentinel
        sentinel = ListNode(0, head)

        # predecessor = the last node
        # before the sublist of duplicates
        pred = sentinel

        while head:
            # If it's the beginning of a duplicates sublist
            # skip all duplicates
            if head.next and head.val == head.next.val:
                # move till the end of duplicates sublist
                while head.next and head.val == head.next.val:
                    head = head.next

                # Skip all duplicates
                pred.next = head.next

            # Otherwise, move predecessor
            else:
                pred = pred.next

            # move forward
            head = head.next

        return sentinel.next

• Time complexity: O(n)
• Space complexity: O(1)