Remove Duplicates in a Un-sorted Linked List
Remove Duplicates in an Unsorted Linked List
Problem Statement
Given an unsorted linked list, remove all duplicate nodes such that each element appears only once. The relative order of the nodes should be preserved.
Example
Input: head = [1, 2, 3, 2, 1, 4]
Output: [1, 2, 3, 4]
Input: head = [5, 2, 2, 4, 5, 6]
Output: [5, 2, 4, 6]
Input: head = [1, 1, 1, 1]
Output: [1]
Brute Force Approach (Two Pointers - No Extra Space)
Intuition
For each node, traverse the rest of the list and remove all occurrences of that value. This uses nested loops but requires no extra space.
Algorithm
- For each node (outer pointer), traverse the remaining list (inner pointer)
- If inner node's value equals outer node's value, remove it
- Continue until end of list
- Return head
Implementation
Complexity Analysis
- Time Complexity: O(n²) - Nested iteration through the list
- Space Complexity: O(1) - No extra space used
Optimal Approach (Using HashSet)
Intuition
We can use a hash set to track values we've seen. As we traverse the list, if we encounter a value already in the set, we remove that node. This trades space for time efficiency.
Algorithm
- Create a hash set to store seen values
- Traverse the list with two pointers (prev and curr)
- If current value is in set, skip the node (prev.next = curr.next)
- If not, add value to set and move prev forward
- Return head
Visualization
Input: 1 -> 2 -> 3 -> 2 -> 1 -> 4 -> null
↑
curr
seen = {}
Step 1: 1 not in seen, add it
seen = {1}, move forward
Step 2: 2 not in seen, add it
seen = {1, 2}, move forward
Step 3: 3 not in seen, add it
seen = {1, 2, 3}, move forward
Step 4: 2 in seen! Remove node
1 -> 2 -> 3 -> 1 -> 4 -> null
↑
curr
Step 5: 1 in seen! Remove node
1 -> 2 -> 3 -> 4 -> null
↑
curr
Step 6: 4 not in seen, add it
seen = {1, 2, 3, 4}
Output: 1 -> 2 -> 3 -> 4 -> null
Implementation
Complexity Analysis
- Time Complexity: O(n) - Single pass through the list
- Space Complexity: O(n) - Hash set stores unique values
Alternative: Sorting Approach
If modifying the order is allowed, we can:
- Sort the linked list (using merge sort) - O(n log n)
- Remove duplicates from sorted list - O(n)
- Total: O(n log n) time, O(1) extra space (if merge sort is done in-place)
However, this changes the relative order of elements.
Implementation
Comparison of Approaches
| Approach | Time | Space | Preserves Order | |----------|------|-------|-----------------| | Two Pointers (Brute Force) | O(n²) | O(1) | Yes | | Hash Set | O(n) | O(n) | Yes | | Sort + Remove | O(n log n) | O(log n)* | No |
*O(log n) for recursive stack in merge sort
Key Takeaways
- Unlike sorted lists, unsorted lists can't use adjacent comparison
- The hash set approach is optimal for time when order must be preserved
- If order doesn't matter, sorting + removal is a valid approach
- The brute force O(n²) approach uses constant space but is slow for large lists
- Always clarify with the interviewer:
- Should the original order be preserved?
- Is extra space allowed?
- This problem demonstrates the classic time-space tradeoff