Problem Description

You are given the head of a linked list that contains integer values. Your task is to identify all values that appear more than once in the linked list and completely remove all nodes containing those duplicate values.

The key points to understand:

• If a value appears multiple times in the linked list, you need to delete all nodes with that value, not just the duplicates
• The linked list is unsorted, meaning duplicate values can appear anywhere in the list
• You need to return the modified linked list after removing all nodes with duplicate values

For example, if you have a linked list like 1 -> 2 -> 3 -> 2 -> 4, the value 2 appears twice. You would need to remove both nodes with value 2, resulting in 1 -> 3 -> 4.

The solution uses a two-pass approach:

1. First pass: Count the frequency of each value using a hash table (Counter). This traverses the entire linked list to identify which values appear more than once.
2. Second pass: Traverse the linked list again, this time removing any node whose value has a count greater than 1 in the hash table.

The code uses a dummy node technique to simplify edge cases (like when the head itself needs to be deleted). It maintains two pointers:

• pre: Points to the node before the current node (used to skip/delete nodes)
• cur: Points to the current node being examined

When a node needs to be deleted (its value count > 1), the code updates pre.next = cur.next to skip over the current node. When a node is kept, pre advances to the current node.

Intuition

The challenge here is that we need to remove all occurrences of values that appear more than once, not just the duplicates. This means we can't simply remove nodes as we encounter duplicates during a single traversal - we need to know upfront which values are duplicated throughout the entire list.

Think about it this way: if we're at a node with value 5, we can't decide whether to keep or delete it without knowing if another 5 exists somewhere else in the list. This naturally leads us to a two-pass strategy.

The first insight is that we need complete information about value frequencies before making any deletion decisions. A hash table is perfect for this - we can traverse the list once and count how many times each value appears. This gives us a "blueprint" of which values need to be eliminated.

The second insight involves the deletion process itself. When traversing a linked list and potentially deleting nodes, we need to maintain connections properly. If we delete a node, we need the previous node to point to the next node, effectively "skipping over" the deleted node. This is why we maintain two pointers: pre (previous) and cur (current).

A clever trick used here is the dummy node. Since we might need to delete the head of the list, having a dummy node before the head simplifies our logic - we don't need special handling for the head deletion case. The dummy node ensures we always have a pre node to work with.

The beauty of this approach is its simplicity: count first, then delete based on counts. By separating the counting phase from the deletion phase, we avoid the complexity of trying to track duplicates while simultaneously modifying the list structure.

Learn more about Linked List patterns.

Solution Approach

The solution uses a hash table to count occurrences and a two-pass traversal strategy to delete nodes with duplicate values.

Step 1: Count Value Frequencies

First, we create a Counter object (hash table) to store the frequency of each value in the linked list:

cnt = Counter()
cur = head
while cur:
    cnt[cur.val] += 1
    cur = cur.next

This traversal visits each node once, incrementing the count for each value encountered. After this pass, cnt contains a mapping of each value to its frequency in the list.

Step 2: Set Up for Deletion

We create a dummy node that points to the head of the list:

dummy = ListNode(0, head)
pre, cur = dummy, head

The dummy node serves as a stable reference point before the actual head. We initialize two pointers:

• pre: starts at the dummy node (always points to the node before cur)
• cur: starts at the head (the current node being examined)

Step 3: Delete Nodes with Duplicate Values

We traverse the list again, checking each node's value against our frequency map:

while cur:
    if cnt[cur.val] > 1:
        pre.next = cur.next  # Skip the current node
    else:
        pre = cur           # Move pre forward only if we keep the node
    cur = cur.next          # Always move cur forward

The deletion logic works as follows:

• If cnt[cur.val] > 1: The value appears multiple times, so we delete this node by updating pre.next = cur.next. Note that pre doesn't move forward in this case.
• If cnt[cur.val] == 1: The value is unique, so we keep the node and advance pre to cur.
• Regardless of deletion, cur always moves to the next node.

Step 4: Return the Modified List

Finally, we return dummy.next, which points to the new head of the modified list. This handles the case where the original head might have been deleted.

The time complexity is O(n) where n is the number of nodes (two passes through the list), and the space complexity is O(n) for the hash table storing value frequencies.

Example Walkthrough

Let's walk through the solution with a concrete example to see how it works step by step.

Given linked list: 3 -> 1 -> 2 -> 3 -> 4 -> 2 -> 5

Step 1: Count Value Frequencies

We traverse the entire list and count each value:

• Node with value 3: count becomes 1
• Node with value 1: count becomes 1
• Node with value 2: count becomes 1
• Node with value 3: count becomes 2 (we've seen 3 before)
• Node with value 4: count becomes 1
• Node with value 2: count becomes 2 (we've seen 2 before)
• Node with value 5: count becomes 1

After the first pass, our frequency map looks like:

cnt = {3: 2, 1: 1, 2: 2, 4: 1, 5: 1}

We've identified that values 3 and 2 appear twice, so all nodes with these values must be removed.

Step 2: Set Up for Deletion

We create a dummy node pointing to the head:

dummy -> 3 -> 1 -> 2 -> 3 -> 4 -> 2 -> 5
^pre     ^cur

Step 3: Delete Nodes with Duplicate Values

Now we traverse again, checking each node against our frequency map:

1. cur = 3: cnt[3] = 2 > 1, so delete this node

   • Set pre.next = cur.next (dummy now points to 1)
   • Move cur to next node (1)
   • pre stays at dummy

   dummy -> 1 -> 2 -> 3 -> 4 -> 2 -> 5
   ^pre     ^cur

2. cur = 1: cnt[1] = 1, so keep this node

   • Move pre to cur (pre now at node 1)
   • Move cur to next node (2)

   dummy -> 1 -> 2 -> 3 -> 4 -> 2 -> 5
            ^pre ^cur

3. cur = 2: cnt[2] = 2 > 1, so delete this node

   • Set pre.next = cur.next (node 1 now points to 3)
   • Move cur to next node (3)
   • pre stays at node 1

   dummy -> 1 -> 3 -> 4 -> 2 -> 5
            ^pre ^cur

4. cur = 3: cnt[3] = 2 > 1, so delete this node

   • Set pre.next = cur.next (node 1 now points to 4)
   • Move cur to next node (4)
   • pre stays at node 1

   dummy -> 1 -> 4 -> 2 -> 5
            ^pre ^cur

5. cur = 4: cnt[4] = 1, so keep this node

   • Move pre to cur (pre now at node 4)
   • Move cur to next node (2)

   dummy -> 1 -> 4 -> 2 -> 5
                 ^pre ^cur

6. cur = 2: cnt[2] = 2 > 1, so delete this node

   • Set pre.next = cur.next (node 4 now points to 5)
   • Move cur to next node (5)
   • pre stays at node 4

   dummy -> 1 -> 4 -> 5
                 ^pre ^cur

7. cur = 5: cnt[5] = 1, so keep this node

   • Move pre to cur (pre now at node 5)
   • Move cur to next node (None)

   dummy -> 1 -> 4 -> 5 -> None
                      ^pre  ^cur

Step 4: Return Result

Return dummy.next, which gives us the final linked list: 1 -> 4 -> 5

All nodes with values that appeared more than once (3 and 2) have been completely removed from the list.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of two passes through the linked list:

• First pass: Traverse the entire linked list to count the frequency of each value using a Counter (hash map). This takes O(n) time where n is the number of nodes in the linked list.
• Second pass: Traverse the linked list again to remove nodes whose values appear more than once. This also takes O(n) time.

Since both passes are sequential and not nested, the overall time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n)

The algorithm uses a Counter (hash map) to store the frequency of each unique value in the linked list. In the worst case, when all values in the linked list are unique, the Counter will store n key-value pairs, requiring O(n) space. The dummy node and pointer variables (pre, cur) only use constant extra space O(1), which doesn't affect the overall space complexity.

Therefore, the space complexity is O(n) where n is the length of the linked list.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly Advancing the previous Pointer

The Problem: A common mistake is to always advance the previous pointer in each iteration, regardless of whether a node was deleted:

# INCORRECT approach
while current:
    if frequency_map[current.val] > 1:
        previous.next = current.next
    else:
        previous.next = current  # Unnecessary
    previous = current  # WRONG: Always advancing previous
    current = current.next

This breaks the deletion logic because when we delete a node, previous should stay in place to potentially delete multiple consecutive nodes with duplicate values.

Example of the bug: For a list 1 -> 2 -> 2 -> 3 where 2 appears twice:

• When we reach the first 2, we set previous.next = current.next (skipping it)
• If we incorrectly advance previous to the deleted node's position, we lose our reference point
• The second 2 won't be properly deleted

The Solution: Only advance previous when we keep a node:

while current:
    if frequency_map[current.val] > 1:
        previous.next = current.next  # Delete node
        # DON'T move previous here
    else:
        previous = current  # Only move previous when keeping a node
    current = current.next

Pitfall 2: Forgetting to Use a Dummy Node

The Problem: Without a dummy node, handling the deletion of the head node becomes complex:

# PROBLEMATIC approach without dummy node
if head and frequency_map[head.val] > 1:
    # Need special logic to handle head deletion
    while head and frequency_map[head.val] > 1:
        head = head.next
    # Then handle the rest of the list...

This leads to code duplication and edge case handling that makes the solution error-prone.

The Solution: Always use a dummy node that points to the head:

dummy_node = ListNode(0, head)
previous = dummy_node
current = head
# Now head deletion is handled uniformly with other deletions

Pitfall 3: Using the Wrong Data Structure for Counting

The Problem: Using a regular dictionary and forgetting to initialize values:

# INCORRECT: May cause KeyError
frequency_map = {}
current = head
while current:
    frequency_map[current.val] += 1  # KeyError if key doesn't exist
    current = current.next

The Solution: Use Counter from collections or properly initialize dictionary values:

# Option 1: Use Counter (recommended)
from collections import Counter
frequency_map = Counter()

# Option 2: Use defaultdict
from collections import defaultdict
frequency_map = defaultdict(int)

# Option 3: Check key existence
frequency_map = {}
while current:
    frequency_map[current.val] = frequency_map.get(current.val, 0) + 1
    current = current.next