LeetCode 1836 - Remove Duplicates From an Unsorted Linked List

LeetCode Problem 1836

Difficulty: 🟡 Medium
Topics: Hash Table, Linked List

Solution

Problem Understanding

This problem gives us the head of a singly linked list whose values are not sorted. Our task is to remove every node whose value appears more than once anywhere in the list.

The important detail is that we are not removing duplicate occurrences while keeping one copy. Instead, if a value appears multiple times, all nodes containing that value must be deleted.

For example, in the list:

1 -> 2 -> 3 -> 2

the value 2 appears twice, so both 2 nodes must be removed. The final list becomes:

1 -> 3

The input represents a standard singly linked list. Each node contains an integer value and a pointer to the next node. The output must also be a linked list, specifically the original list after removing all nodes whose values occur more than once.

The constraints are important:

• The list can contain up to 10^5 nodes
• Node values are also bounded by 10^5

These limits immediately tell us that an inefficient nested-loop solution will likely time out. An O(n^2) approach would perform up to 10^10 operations in the worst case, which is far too slow. This strongly suggests that we need a linear or near-linear solution.

Several edge cases are especially important:

• A list where every value is unique, the list should remain unchanged.
• A list where every value is duplicated, the result should be an empty list.
• Duplicates may appear non-consecutively because the list is unsorted.
• The head node itself may need to be removed.
• Multiple duplicated values may appear throughout the list.

Because the list is unsorted, we cannot rely on adjacent comparisons like we would in a sorted linked list problem. We need a way to count occurrences globally across the entire list.

Approaches

Brute Force Approach

A straightforward solution is to examine every node and count how many times its value appears in the entire list.

For each node:

1. Traverse the whole list again.
2. Count occurrences of that node's value.
3. If the count is greater than one, remove the node.

This approach is correct because every node is checked against every other node, guaranteeing accurate frequency counts.

However, the performance is poor. If the list contains n nodes, then for each node we may scan all n nodes again. This leads to O(n^2) time complexity.

With up to 100000 nodes, this approach is impractical.

Optimal Approach

The key observation is that the problem only depends on how many times each value appears in the entire list.

Instead of repeatedly recounting frequencies, we can:

1. Make one pass through the list to build a frequency map.
2. Make a second pass to remove nodes whose frequency is greater than one.

A hash map is ideal here because it allows constant-time average lookup and insertion.

The algorithm becomes:

• First pass: count frequencies.
• Second pass: rebuild the linked list using only values that appear exactly once.

This reduces the time complexity to linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Recounts occurrences for every node
Optimal	O(n)	O(n)	Uses a hash map to store frequencies

Algorithm Walkthrough

Optimal Algorithm

1. Create a hash map called frequency.

This map will store how many times each value appears in the linked list. 2. Traverse the linked list once to populate the frequency map.

For every node:

• Read node.val
• Increment its count in the hash map

After this pass, we know exactly which values are duplicated. 3. Create a dummy node before the head.

A dummy node simplifies deletion logic, especially when the original head itself must be removed. 4. Initialize two pointers:

• prev, initially pointing to the dummy node
• current, initially pointing to the head

5. Traverse the linked list again.

For each node:

• Look up frequency[current.val]

• If the frequency is greater than one:

• Skip the node by setting prev.next = current.next

• Otherwise:

• Keep the node and move prev forward

6. Move current forward after each iteration.
7. Return dummy.next.

This correctly handles all cases, including when the original head was removed.

Why it works

The frequency map guarantees that we know whether a value appears once or multiple times across the entire list. During the second traversal, every node with a duplicated value is removed, while every unique value is preserved. Since every node is processed exactly once in each pass, the resulting linked list contains precisely the nodes whose values appeared exactly once in the original list.

Python Solution

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

from typing import Optional
from collections import defaultdict

class Solution:
    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:
        frequency = defaultdict(int)

        current = head

        # First pass: count frequencies
        while current:
            frequency[current.val] += 1
            current = current.next

        dummy = ListNode(0)
        dummy.next = head

        prev = dummy
        current = head

        # Second pass: remove duplicated values
        while current:
            if frequency[current.val] > 1:
                prev.next = current.next
            else:
                prev = current

            current = current.next

        return dummy.next

The implementation follows the exact two-pass strategy described earlier.

The first section creates a frequency map using defaultdict(int). This allows counts to be incremented without checking whether a key already exists.

The first traversal walks through the entire linked list and records how many times each value appears.

Next, a dummy node is created. This is a common linked list technique that simplifies node deletion logic. Without a dummy node, removing the head would require special handling.

The second traversal examines each node again. If the node's value appears more than once, the node is skipped by reconnecting prev.next directly to current.next. Otherwise, the node remains in the list and prev advances normally.

Finally, dummy.next is returned because the actual head of the filtered list may differ from the original head.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicatesUnsorted(head *ListNode) *ListNode {
    frequency := make(map[int]int)

    current := head

    // First pass: count frequencies
    for current != nil {
        frequency[current.Val]++
        current = current.Next
    }

    dummy := &ListNode{Next: head}

    prev := dummy
    current = head

    // Second pass: remove duplicated values
    for current != nil {
        if frequency[current.Val] > 1 {
            prev.Next = current.Next
        } else {
            prev = current
        }

        current = current.Next
    }

    return dummy.Next
}

The Go implementation is structurally identical to the Python version.

Go uses a built-in map with type map[int]int for frequency counting. Since Go does not have Python's defaultdict, missing keys automatically return the zero value for integers, which makes incrementing straightforward.

The dummy node is allocated using:

dummy := &ListNode{Next: head}

Pointer manipulation works similarly to Python references, but Go requires explicit pointer syntax.

The implementation safely handles nil pointers and correctly removes nodes even when the head must be deleted.

Worked Examples

Example 1

Input:

1 -> 2 -> 3 -> 2

First Pass: Frequency Counting

Node Value	Frequency Map
1	{1: 1}
2	{1: 1, 2: 1}
3	{1: 1, 2: 1, 3: 1}
2	{1: 1, 2: 2, 3: 1}

Second Pass: Removal

Current Node	Frequency	Action	Resulting List
1	1	Keep	1 -> 2 -> 3 -> 2
2	2	Remove	1 -> 3 -> 2
3	1	Keep	1 -> 3 -> 2
2	2	Remove	1 -> 3

Final output:

1 -> 3

Example 2

Input:

2 -> 1 -> 1 -> 2

First Pass: Frequency Counting

Node Value	Frequency Map
2	{2: 1}
1	{2: 1, 1: 1}
1	{2: 1, 1: 2}
2	{2: 2, 1: 2}

Second Pass: Removal

Current Node	Frequency	Action
2	2	Remove
1	2	Remove
1	2	Remove
2	2	Remove

Final output:

[]

Example 3

Input:

3 -> 2 -> 2 -> 1 -> 3 -> 2 -> 4

First Pass: Frequency Counting

Value	Count
3	2
2	3
1	1
4	1

Second Pass: Removal

Current Node	Frequency	Action	Current Result
3	2	Remove	2 -> 2 -> 1 -> 3 -> 2 -> 4
2	3	Remove	2 -> 1 -> 3 -> 2 -> 4
2	3	Remove	1 -> 3 -> 2 -> 4
1	1	Keep	1 -> 3 -> 2 -> 4
3	2	Remove	1 -> 2 -> 4
2	3	Remove	1 -> 4
4	1	Keep	1 -> 4

Final output:

1 -> 4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Two linear passes through the linked list
Space	O(n)	Hash map stores frequencies for up to n distinct values

The algorithm performs exactly two traversals of the linked list. Each traversal visits every node once, resulting in linear time complexity.

The additional memory comes from the frequency map. In the worst case, every node contains a unique value, so the map stores n entries.

Test Cases

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

def build_list(values):
    dummy = ListNode(0)
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

def list_to_array(head):
    result = []

    while head:
        result.append(head.val)
        head = head.next

    return result

solution = Solution()

# Example 1
head = build_list([1, 2, 3, 2])
assert list_to_array(solution.deleteDuplicatesUnsorted(head)) == [1, 3]  # remove duplicated 2s

# Example 2
head = build_list([2, 1, 1, 2])
assert list_to_array(solution.deleteDuplicatesUnsorted(head)) == []  # all values duplicated

# Example 3
head = build_list([3, 2, 2, 1, 3, 2, 4])
assert list_to_array(solution.deleteDuplicatesUnsorted(head)) == [1, 4]  # multiple duplicated values

# Single node
head = build_list([5])
assert list_to_array(solution.deleteDuplicatesUnsorted(head)) == [5]  # single unique node

# All unique values
head = build_list([1, 2, 3, 4])
assert list_to_array(solution.deleteDuplicatesUnsorted(head)) == [1, 2, 3, 4]  # unchanged list

# All duplicated values
head = build_list([7, 7, 7, 7])
assert list_to_array(solution.deleteDuplicatesUnsorted(head)) == []  # everything removed

# Duplicates at the head
head = build_list([1, 1, 2, 3])
assert list_to_array(solution.deleteDuplicatesUnsorted(head)) == [2, 3]  # head removed

# Duplicates at the tail
head = build_list([1, 2, 3, 3])
assert list_to_array(solution.deleteDuplicatesUnsorted(head)) == [1, 2]  # tail removed

# Non-consecutive duplicates
head = build_list([1, 2, 3, 1, 4])
assert list_to_array(solution.deleteDuplicatesUnsorted(head)) == [2, 3, 4]  # unsorted duplicate handling

# Large repeated blocks
head = build_list([5, 5, 6, 6, 7, 8, 8])
assert list_to_array(solution.deleteDuplicatesUnsorted(head)) == [7]  # only one unique value remains

Test	Why
[1,2,3,2]	Basic duplicate removal
[2,1,1,2]	Entire list removed
[3,2,2,1,3,2,4]	Multiple duplicated values
[5]	Smallest valid input
[1,2,3,4]	No removals needed
[7,7,7,7]	Every node removed
[1,1,2,3]	Head deletion handling
[1,2,3,3]	Tail deletion handling
[1,2,3,1,4]	Non-adjacent duplicates
[5,5,6,6,7,8,8]	Only one unique node survives

Edge Cases

One important edge case occurs when the head node itself must be removed. For example:

1 -> 1 -> 2 -> 3

A naive implementation may lose track of the new head after deletion. The dummy node solves this problem cleanly by providing a stable node before the head. After removals, dummy.next always points to the correct new head.

Another tricky case is when all nodes are duplicates:

2 -> 2 -> 3 -> 3

In this situation, the final list should be empty. Some implementations incorrectly leave dangling references or fail to return None. Because the algorithm reconnects pointers carefully and returns dummy.next, the result correctly becomes an empty list.

Non-consecutive duplicates are also easy to mishandle:

1 -> 2 -> 3 -> 1

Since the list is unsorted, duplicates are not necessarily adjacent. Algorithms that only compare neighboring nodes will fail here. The frequency map guarantees global counting across the entire list, ensuring all duplicated values are removed regardless of position.

A final important edge case is a list with only unique values. In this case, no nodes should be removed, and the original structure should remain intact. The algorithm handles this naturally because every frequency count equals one, so all nodes are preserved during the second traversal.