Remove Duplicates from Sorted List II

Intuition

Because the list is sorted, all copies of a value sit next to each other, which makes duplicates easy to detect by comparing a node with its immediate successor. If the head shares its value with the next node, the head is part of a duplicated run, so we advance past every node carrying that value and recurse from the first node with a new value; none of the skipped nodes belong in the answer. If the head's value differs from the next node's value, the head is unique so far, so we keep it and simply recurse on the remainder, wiring the returned list into head.next. The base case of an empty or single-node list needs no work.

Algorithm walkthrough

1. 1Base case: if head or head.next is null, return head since a run of duplicates needs at least two nodes.
2. 2If head.val equals head.next.val, record that value and walk head forward while it keeps matching, discarding the whole duplicate block.
3. 3Return the recursive result on the first node whose value differs, since the entire matched block is excluded from the answer.
4. 4Otherwise head is distinct: set head.next to the recursive result on head.next to clean the rest of the list.
5. 5Return head, now guaranteed to be a unique value followed by an already-deduplicated tail.

Implementation

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        if head.val == head.next.val:
            val = head.val
            while head and head.val == val:
                head = head.next
            return self.deleteDuplicates(head)
        head.next = self.deleteDuplicates(head.next)
        return head