DSA problem
Remove Duplicates from Sorted List
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list still sorted.
Because the list is already sorted in non-decreasing order, every group of equal values occupies a contiguous run of nodes. This means you never need to look more than one step ahead: any duplicate of the current node, if it exists, is its immediate successor. That property turns what could be an expensive comparison problem into a simple single-pass scan.
Note the distinction from the harder variant of this problem: here you keep exactly one copy of each value rather than discarding every value that appears more than once. So a run of three nodes with value 1 collapses to a single node with value 1.
The optimal approach walks a single current pointer through the list. At each step, if current.next holds the same value as current, splice out that next node by setting current.next = current.next.next; otherwise advance current. Because the head of the result is never deleted, no dummy node is needed, and the whole list is cleaned in one O(n) pass using O(1) extra space.
Examples
head = [1,1,2][1,2]head = [1,1,2,3,3][1,2,3]head = [][]Constraints
- The number of nodes in the list is in the range [0, 300].
- -100 <= Node.val <= 100
- The list is guaranteed to be sorted in non-decreasing order.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.