Remove Duplicates from Sorted List II – Python Solution

Problem Description

So, you’ve got a sorted linked list, and it’s looking a bit too crowded with duplicates. Imagine you’re at a party, and there are way too many people wearing the same outfit. You can’t tell who’s who! The task here is to remove all nodes that have duplicate values, leaving only distinct numbers. In other words, if someone is wearing the same outfit as someone else, they both get kicked out of the party.

Example

Input: 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5

Output: 1 -> 2 -> 5

In this case, the numbers 3 and 4 were duplicates, so they were shown the door.

Code Solution

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

        while head:
            while head.next and head.val == head.next.val:
                head = head.next
            if prev.next == head:
                prev = prev.next
            else:
                prev.next = head.next
            head = head.next

        return dummy.next

Approach

The approach here is quite straightforward. We use a dummy node to simplify the handling of edge cases, such as when the head of the list itself is a duplicate. We traverse the list, checking for duplicates. If we find any, we skip over them. If we don’t find any duplicates, we simply move the prev pointer forward. This way, we maintain a clean list without duplicates.

Time and Space Complexity

Complexity	Details
Time Complexity	O(n), where n is the number of nodes in the linked list. We traverse the list once.
Space Complexity	O(1), since we are using a constant amount of space (the dummy node and a few pointers).

Real-World Example

Think of a grocery store where you have a list of items to buy. If you accidentally wrote down “apples” three times, you’d want to cross out the duplicates before heading to the store. This problem is just like that! You want to ensure that your shopping list (or linked list, in this case) has only unique items.