LeetCode Solutions Blog

Remove Duplicates from Sorted List II

Difficulty: Medium

Problem Description

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.

Key Insights

The linked list is sorted, which allows for an efficient traversal.
We need to identify duplicates by comparing adjacent nodes.
A dummy node can help simplify edge cases, such as when the head itself is a duplicate.

Space and Time Complexity

Time Complexity: O(n) - We traverse the list once. Space Complexity: O(1) - We use a constant amount of extra space.

Solution

To solve the problem, we will use a two-pointer approach with a dummy node. The dummy node will point to the head of the new list we are constructing. We will traverse the original linked list while checking for duplicates. If a node is a duplicate, we skip over all nodes with that value. If it's unique, we add it to the new list. This approach ensures that we only keep nodes with distinct values.

Code Solutions

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def deleteDuplicates(head: ListNode) -> ListNode:
    # Create a dummy node to handle edge cases
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy  # Previous node starts at dummy
    current = head  # Current node starts at head

    while current:
        # Check if current node is a start of duplicates
        if current.next and current.val == current.next.val:
            # Skip all nodes with the same value
            while current.next and current.val == current.next.val:
                current = current.next
            # Connect prev to the next distinct node
            prev.next = current.next
        else:
            # No duplicates detected, move prev to current
            prev = current
        # Move current to the next node
        current = current.next

    return dummy.next