Remove Duplicates from Sorted List II

Solution

Iteration

Check if curr.next.val == curr.next.next.val. If so, keep deleting duplicate nodes.

Complexity

time: $O(n)$
space: $O(1)$

def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(next=head)
    curr = dummy
    while curr.next and curr.next.next:
        val = curr.next.val
        if val == curr.next.next.val:
            while curr.next and val == curr.next.val:
                curr.next = curr.next.next
        else:
            curr = curr.next
    return dummy.next

Recursion

Always pass the next non-duplicate node to next recursion.

def deleteDuplicates(self, head: ListNode) -> ListNode:
    if not head: return None
    if head.next and head.val == head.next.val:
        while head.next and head.val == head.next.val:
            head = head.next
        return self.deleteDuplicates(head.next)
    else:
        head.next = self.deleteDuplicates(head.next)
    return head

Or have two recursions. In rm remove all duplicate nodes and return the non duplicate one.

def deleteDuplicates(self, head: ListNode) -> ListNode:
    if not head: return None
    if head.next and head.val == head.next.val:
        return self.deleteDuplicates(self.rm(head, head.val))
    head.next = self.deleteDuplicates(head.next)
    return head

def rm(self, dup_node: ListNode, dup_val: int) -> ListNode:
    if dup_node and dup_node.val == dup_val:
        return self.rm(dup_node.next, dup_val)
    else:
        return dup_node