We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Remove Duplicates from Sorted List II

Number: 82

Difficulty: Medium

Paid? No

Companies: Meta, Microsoft, Google, Oracle, Bloomberg, Amazon, Apple

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. The returned linked list should also remain sorted.

Key Insights

  • The list is sorted, so duplicate nodes appear consecutively.
  • Use a dummy node to simplify edge cases (e.g., when the first node is a duplicate).
  • Two pointers (prev and current) can be used to detect and skip over duplicate nodes.
  • If a node has duplicates, skip all nodes with that value and connect the previous valid node to the next distinct node.

Space and Time Complexity

Time Complexity: O(n) - We traverse the list once. Space Complexity: O(1) - Only a few pointers are used, regardless of the input size.

Solution

We iterate through the linked list with a pointer called current while maintaining a previous pointer (prev) initialized to a dummy node. Whenever we detect that the current node has a duplicate (i.e., its next node has the same value), we record that value and advance current until all nodes with that duplicate value are skipped. Then, we link the previous node to the current node (which is now the next distinct node). If no duplicate is found, we simply move both pointers forward. This approach efficiently removes all duplicates in one pass with constant extra space.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        # Create a dummy node to handle edge cases.
        dummy = ListNode(0)
        dummy.next = head
        
        # Initialize pointers: prev for the last confirmed non-duplicate node, current for traversal.
        prev = dummy
        current = head
        
        while current:
            # If the current node is the start of duplicates.
            if current.next and current.val == current.next.val:
                duplicate_val = current.val
                # Skip all nodes with this duplicate value.
                while current and current.val == duplicate_val:
                    current = current.next
                # Link the last non-duplicate node to the next distinct node.
                prev.next = current
            else:
                # No duplicate: move prev pointer to current.
                prev = current
                current = current.next
                
        # Return the modified linked list.
        return dummy.next
← Back to All Questions