Remove Duplicates from Sorted List
Delete duplicates from a sorted list so each value appears once.
- 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 ascending order.
Intuition
Remove duplicates from sorted list deletes duplicate values from a sorted linked list, leaving one copy of each. Because the list is sorted, duplicates are adjacent, so comparing each node with its immediate successor is sufficient.
The operation is simpler than most linked-list problems because the head can never be removed. One copy of every value survives, and the first node is always the first copy of its value — so no dummy node is needed, which is unusual for a deletion problem:
- Walk the list comparing each node to its next; when the values match, unlink the successor by pointing past it.
The critical detail is what happens after a removal. When current.next is unlinked, current must not advance — the newly linked successor may also be a duplicate. Advancing unconditionally skips it, and a run of three identical values leaves two behind.
So the pointer moves only when the values differ. That single condition handles runs of any length without a nested loop.
The loop condition must check both current and current.next, since the comparison dereferences the successor. Checking only current faults on the final node.
An empty list or a single node returns unchanged — the loop condition fails immediately and the head is returned as-is.
The head is always returned, never a dummy's next, because the original head always survives.
Remove Duplicates from Sorted List II removes all copies of any duplicated value, keeping none. That version does need a dummy node, since the head itself can be deleted — a useful contrast.
One pass gives O(n) time and O(1) space.
Because the list is sorted, duplicates are adjacent — so comparing each node to its immediate successor is enough. No dummy head is needed here, since the first node is always kept.
Approach
Before reading on: price up what sorting first costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(n) time and O(1) space.
Use the sorted order
Duplicates are adjacent in a sorted list, so comparing each node with its immediate successor catches every one.
Skip the dummy node
The head always survives, since one copy of each value is kept. No dummy is needed — unusual for a deletion problem.
Unlink the duplicate successor
When values match, set current.next = current.next.next, bypassing the duplicate node entirely.
Do not advance after removing
Stay on the current node after unlinking — the new successor may also be a duplicate. Advancing leaves two nodes behind in a run of three.
Advance only on a difference
Move forward when the values differ. This single condition handles runs of any length without a nested loop.
Guard both pointers
Loop while both current and current.next exist, since the comparison dereferences the successor. Checking only current faults on the last node.
Cost of the approach
One pass relinking pointers gives O(n) time and O(1) space. The variant removing all copies needs a dummy, since the head can be deleted.
Solution & live demo
Common pitfalls
Advancing after unlinking
if cur.next.val == cur.val:
cur.next = cur.next.next
cur = cur.nextif cur.next.val == cur.val:
cur.next = cur.next.next
else:
cur = cur.nextThree or more equal values in a row need repeated unlinking from the same position. Advancing unconditionally skips past the newly linked node and leaves a duplicate.
Adding a dummy head
dummy = ListNode(0) dummy.next = head
cur = head
Harmless but unnecessary — unlike the remove-by-value problem, the head is never deleted here because it's the first occurrence of its value. The dummy adds a node and a return-value subtlety for nothing.
Checking only cur in the loop condition
while cur:
while cur and cur.next:
The body dereferences cur.next.val, so the successor must exist. Testing only cur throws on the final node.
Edge cases
Collapses to a single node.
The pointer advances every step and the list is unchanged.
Staying on cur after a deletion collapses the whole run.
The loop condition fails immediately; return head.