Remove Duplicates from Sorted List
Understanding the Problem
We have a linked list where nodes are already sorted in ascending order. Some nodes have duplicate values, and we need to remove the extra copies so that each value appears exactly once. The output should still be a sorted linked list.
Because the list is sorted, all duplicates are grouped together. To decide whether a node is a duplicate, we only compare it with the one right next to it. If they share the same value, the next node is a duplicate, and we remove it by adjusting pointers.
Removing an element from a linked list is a matter of relinking the next pointer. There is no shifting of later elements the way there would be in an array.
Key Constraints:
0 <= number of nodes <= 300→ The list can be empty (0 nodes), so we handle a null head before dereferencing it.Sorted in ascending order→ This constraint drives the optimal approach. Duplicates are always consecutive, so comparingcurrent.valwithcurrent.next.valis enough to detect every one of them.
Approach 1: Using a Hash Set
Intuition
Use a hash set to track which values we have already seen. Walk through the list, and for each node, check whether its next node's value is in the set. If it is, remove that node. If not, add the value to the set and keep the node.
This approach ignores the fact that the list is sorted, so it also works on an unsorted list. The cost is the extra memory for the set, which the sorted version avoids.
Algorithm
- If the list is empty, return
null. - Create a hash set and add the head node's value to it.
- Walk through the list, keeping track of the current node.
- For each node, if its next node's value is already in the set, remove the next node by setting
current.next = current.next.next. - If the next node's value is new, add it to the set and move
currentforward. - Return the head.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node exactly once. Hash set lookups and insertions are O(1) on average, so the total is O(n).
- Space Complexity: O(n). The hash set stores up to n unique values in the worst case (when there are no duplicates).
Because the list is sorted, duplicates are always adjacent, so the hash set is not needed. The next approach detects them with a single neighbor comparison and uses no extra space.
Approach 2: Single Pass In-Place (Optimal)
Intuition
In a sorted list, duplicates sit next to each other, so there is no need to remember every value we have encountered. Comparing each node with the one directly after it is enough.
Walk through the list with a single pointer. At each node, look at its next neighbor. If they share the same value, the neighbor is a duplicate, so we remove it by relinking the pointer. If they differ, we move forward.
Sorted order guarantees that all nodes with the same value form one contiguous run. A comparison of current.val with current.next.val therefore catches every duplicate, because two equal values can never be separated by a different value. When current does not advance after a skip, its next pointer already references the node past the removed one, so the following iteration compares current against the new neighbor and removes the rest of the run before moving on.
Relinking with current.next = current.next.next removes a node in constant time, with no shifting of later elements.
Algorithm
- If the list is empty, return
null. - Start with a pointer
currentat the head. - While
currentandcurrent.nextboth exist: - If
current.val == current.next.val, skip the next node by settingcurrent.next = current.next.next. - Otherwise, move
currentforward tocurrent.next. - Return the head.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node at most once. In the worst case (no duplicates), we traverse all n nodes. In the best case (all duplicates), we still traverse n nodes but skip most of them.
- Space Complexity: O(1). We only use a single pointer
current. No extra data structures, no recursion stack.