#83
Remove Duplicates from Sorted List
Easy In-place unlink
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Delete duplicate nodes from a sorted linked list so each value appears once.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: keep one node per value in a sorted list.
Why this works: duplicates sit together; skip cur.next while it repeats cur's value.
Example: 1 → 1 → 2 → 3 → 3
skip second 1, skip second 3 → 1 → 2 → 3✦Hints open one at a time
Duplicates are adjacent.
If cur.next has the same value, skip it by pointing cur.next past it — and don't move cur yet.
↗Approach
Walk with cur; while cur.next has the same value, unlink it. Otherwise move cur forward.
</>Solution (Java)
/**
* class ListNode { int val; ListNode next; } // provided by LeetCode
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while (cur != null && cur.next != null) {
if (cur.next.val == cur.val) cur.next = cur.next.next; // stay on cur
else cur = cur.next;
}
return head;
}
}!Common mistake
Moving cur forward after unlinking, which misses a third copy.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Linked List
🎬 Episodes 40–45: video coming soon