LinkedListProblem 6 of 36
Remove Duplicates in a sorted Linked List
Remove Duplicates in a Sorted Linked List
Problem Statement
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
Example
Input: head = [1, 1, 2]
Output: [1, 2]
Input: head = [1, 1, 2, 3, 3]
Output: [1, 2, 3]
Input: head = [1, 1, 1, 1, 1]
Output: [1]
Brute Force Approach (Using Set)
Intuition
We can traverse the list and store unique values in a set (or create a new list with unique values). However, since the list is already sorted, this approach doesn't leverage the sorted property.
Algorithm
- Create a set to track 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 to set and move prev forward
- Return head
Implementation
Complexity Analysis
- Time Complexity: O(n) - Single pass through the list
- Space Complexity: O(n) - Set stores unique values
Optimal Approach (Two Pointer - In Place)
Intuition
Since the list is sorted, all duplicates are consecutive. We can simply compare each node with its next node. If they're equal, skip the next node; otherwise, move forward.
Algorithm
- Start with current pointer at head
- While current and current.next exist:
- If current.val == current.next.val, skip the next node
- Otherwise, move current to the next node
- Return head
Visualization
Input: 1 -> 1 -> 2 -> 3 -> 3 -> null
↑
curr
Step 1: curr.val (1) == curr.next.val (1)
Skip: 1 -> 2 -> 3 -> 3 -> null
↑
curr
Step 2: curr.val (1) != curr.next.val (2)
Move: 1 -> 2 -> 3 -> 3 -> null
↑
curr
Step 3: curr.val (2) != curr.next.val (3)
Move: 1 -> 2 -> 3 -> 3 -> null
↑
curr
Step 4: curr.val (3) == curr.next.val (3)
Skip: 1 -> 2 -> 3 -> null
↑
curr
Output: 1 -> 2 -> 3 -> null
Implementation
Complexity Analysis
- Time Complexity: O(n) - Single pass through the list
- Space Complexity: O(1) - Only using constant extra space
Variant: Remove All Duplicates (Keep No Duplicates)
A harder variant: Remove all nodes that have duplicate values, leaving only distinct numbers.
Input: 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
Output: 1 -> 2 -> 5
Implementation
Key Takeaways
- Sorted property is key - duplicates are always consecutive
- The optimal solution requires only O(1) extra space
- Be careful not to move the pointer when deleting (compare again with new next)
- The variant (remove all duplicates) requires a dummy node for edge cases
- This is a common warm-up problem before harder linked list questions
- Remember to free memory in C++ when deleting nodes