Skip to main content
Talentd

Remove Duplicates From an Unsorted Linked List - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableLinked List7 min readAsked at: Amazon, Microsoft
Practice this problem

Problem Statement

Given the head of a linked list, find all the values that appear more than once in the list and delete the nodes that have any of those values.

Return the linked list after the deletions.

 

Example 1:


Input: head = [1,2,3,2]

Output: [1,3]

Explanation: 2 appears twice in the linked list, so all 2's should be deleted. After deleting all 2's, we are left with [1,3].

Example 2:


Input: head = [2,1,1,2]

Output: []

Explanation: 2 and 1 both appear twice. All the elements should be deleted.

Example 3:


Input: head = [3,2,2,1,3,2,4]

Output: [1,4]

Explanation: 3 appears twice and 2 appears three times. After deleting all 3's and 2's, we are left with [1,4].

 

Constraints:

  • The number of nodes in the list is in the range [1, 105]
  • 1 <= Node.val <= 105

Approach Overview

Problem Overview: Given the head of an unsorted linked list, remove every node whose value appears more than once. Only values that occur exactly once should remain in the final list. The list is not sorted, so duplicates may appear anywhere in the structure.

Approach 1: Brute Force Comparison (O(n²) time, O(1) space)

The straightforward idea is to check every node against the rest of the list. For each node, iterate through the entire linked list and count how many times its value appears. If the count is greater than one, remove that node from the list using pointer manipulation. This approach requires two nested traversals of the list, leading to O(n²) time complexity. Space usage remains O(1) because no additional data structures are used. While inefficient for large lists, it demonstrates a solid understanding of linked list traversal and pointer updates.

Approach 2: Hash Table Frequency Counting (O(n) time, O(n) space)

The optimal solution uses a hash table to track how often each value appears. First pass: iterate through the list and store the frequency of every node value in a hash map. Each insertion or lookup in the map takes constant time on average, so the full pass costs O(n). Second pass: traverse the list again while maintaining a previous pointer. If the frequency of the current node’s value is greater than one, remove the node by updating prev.next. Otherwise, move the pointer forward.

This two-pass strategy cleanly separates counting from removal. The hash map allows constant-time frequency checks, eliminating the need for repeated scans. The total runtime becomes O(n), and the extra memory used by the map is O(n). This tradeoff is usually acceptable because the algorithm scales efficiently even for large lists.

Careful pointer handling is required when deleting nodes, especially near the head of the list. Many implementations use a dummy node before the head to simplify removal logic. The dummy node ensures that deleting the first real node does not require special-case handling.

Recommended for interviews: The hash table approach is what interviewers typically expect. It demonstrates the ability to combine hash-based frequency counting with standard linked list traversal. Mentioning the brute force solution first shows problem exploration, but implementing the O(n) hash map solution shows strong algorithmic judgment and practical engineering thinking.

Solution

We can use a hash table cnt to count the number of occurrences of each element in the linked list, and then traverse the linked list to delete elements that appear more than once.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the linked list.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Nested TraversalO(n²)O(1)When extra memory cannot be used and the list size is small
Hash Table Frequency CountO(n)O(n)General case and interview-preferred solution for unsorted lists

Video Solution

Big Tech Coding Interview - Remove Duplicates from Unsorted Linked List - 1836 • AlgoJS • 2,266 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Remove Duplicates From an Unsorted Linked List easy or hard?
The problem is generally classified as Medium difficulty. It requires combining hash table frequency counting with careful linked list pointer manipulation, which is slightly more involved than basic traversal problems.
Remove Duplicates From an Unsorted Linked List Python/Java solution
Implement a two-pass algorithm. In the first pass, store value counts in a dictionary (Python) or HashMap (Java). In the second pass, traverse the list with a dummy node and remove any node whose frequency is greater than one.
How to solve Remove Duplicates From an Unsorted Linked List in O(n)?
Use a hash map to record how many times each value appears in the list. After building the frequency map in one traversal, iterate through the list again and delete any node whose value appears more than once. Each node is processed a constant number of times, resulting in O(n) time complexity.
What is the best approach for Remove Duplicates From an Unsorted Linked List?
The most efficient approach uses a hash table to count how many times each value appears in the linked list. First traverse the list to build a frequency map, then perform a second pass to remove nodes whose frequency is greater than one. This method runs in O(n) time with O(n) extra space.
Is Remove Duplicates From an Unsorted Linked List asked at Google/Amazon/Meta?
Linked list deduplication and frequency-based removal problems commonly appear in interviews at companies like Amazon, Google, and Meta. Variations test knowledge of hash tables, pointer manipulation, and efficient list traversal.
What data structure is used in Remove Duplicates From an Unsorted Linked List?
The optimal solution relies on a hash table (or hash map) to store value frequencies. The linked list itself is traversed while pointers are adjusted to remove nodes with duplicate values.
What is the time complexity of Remove Duplicates From an Unsorted Linked List?
The optimal solution runs in O(n) time because the linked list is traversed twice: once to count frequencies and once to remove duplicate nodes. Hash table operations are O(1) on average. A naive brute force solution would take O(n²) time due to repeated scanning of the list.

Ready to solve this problem?

Practice Remove Duplicates From an Unsorted Linked List with our built-in code editor and test cases.

Practice on FleetCode
Previous

Remove Duplicates from Sorted List

Next

Remove Duplicates from Sorted List II