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 an Unsorted Linked List

Number: 1982

Difficulty: Medium

Paid? Yes

Companies: Microsoft

Problem Description

Given the head of a linked list, remove all nodes that contain values appearing more than once. Only values that occur exactly once should remain in the linked list.

Key Insights

  • A first pass through the linked list can be used to count the frequency of each value.
  • Using a hash table (or dictionary) for counting frequencies supports O(n) time access.
  • A dummy node simplifies edge cases (such as updates at the head) when deleting nodes.
  • In a second pass, build the resulting list by skipping nodes with a frequency greater than 1.

Space and Time Complexity

Time Complexity: O(n) - We traverse the list twice (once for counting and once for filtering). Space Complexity: O(n) - A hash table stores counts for up to n unique values.

Solution

We first traverse the linked list to count the occurrence of each node's value using a hash table. After obtaining the frequency of every value, we use a dummy node to start building the new linked list. We traverse again, and if a node's value has a frequency of 1, we attach it to the new list; otherwise, we skip it. This two-pass approach ensures that all nodes with duplicate values are removed while handling edge cases (like removing the head node) gracefully.

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:
        # First pass: count the frequency of each value in the linked list.
        freq = {}
        current = head
        while current:
            freq[current.val] = freq.get(current.val, 0) + 1
            current = current.next
        
        # Dummy node to simplify edge cases.
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        current = head
        
        # Second pass: remove nodes that have frequency more than 1.
        while current:
            if freq[current.val] > 1:
                # Skip the current node because its value is a duplicate.
                prev.next = current.next
            else:
                # Otherwise, keep the node.
                prev = current
            current = current.next
            
        return dummy.next
← Back to All Questions