Problem Statement in English

You’re 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.

Approach

We can use a dummy node to simplify edge cases, especially when the head itself might be a duplicate. We maintain a pointer prev that points to the last node in the result list (the list without duplicates). We iterate through the original list with a pointer head.

If we encounter a node that has the same value as the next node, we skip all nodes with that value, and set prev.next to the node after the last duplicate, but don’t move prev forward.

If the current node is unique (i.e., its value is different from the next node), we move prev forward to include this node in the result list.

And we’re done!

Solution in Python


class Solution:
    def deleteDuplicates(self, head: ListNode | None) -> ListNode | None:
        dummy = ListNode(0, head)
        prev = dummy

        while head:
            # Check if current node has duplicates
            if head.next and head.val == head.next.val:
                # Skip all nodes with the same value
                while head.next and head.val == head.next.val:
                    head = head.next
                # Connect prev past all duplicates
                prev.next = head.next
            else:
                # Move prev forward if head was unique
                prev = prev.next

            head = head.next

        return dummy.next

Complexity

  • Time: $O(n)$
    Since we are iterating through the entire linked list once, the time complexity is linear with respect to the number of nodes in the list.

  • Space: $O(1)$
    Since we are using a constant amount of extra space (only a few pointers), the space complexity is constant.

And we are done.