Remove Duplicates from Sorted List
Easy · Linked Lists · Linked List
Problem
You are given the head of a linked list sorted in non-decreasing order. Remove the repeated nodes so that every value appears exactly once, and return the head of the list, which stays sorted.
The node type and two helpers are already defined for you:
Examples
Input: head = [1,1,2,3,3] Output: [1,2,3]
The extra copies of 1 and 3 are unlinked.
Input: head = [4,4,4] Output: [4]
Only one 4 remains.
Input: head = [] Output: []
An empty list has nothing to remove.
Constraints
- 0 <= number of nodes <= 300
- -100 <= Node.val <= 100
- The list is sorted in non-decreasing order.
Approaches
- Baseline: collect distinct values, build a new list — time O(n), space O(n)
Follow-up
Sorting is what makes a single comparison with the next node enough. The use cases allow up to k copies of each value, and remove repeats from a list that is not sorted.
Related problems
Start free on Cariara · Coding problems · System design studio
