Remove Duplicates from Sorted List II — Problem & Solution
Remove Duplicates from Sorted List II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Remove Duplicates from Sorted List II is a medium coding problem on two pointers, asked in Amazon, Microsoft, Meta and Bloomberg interviews.
- Difficulty: Medium
- Topics: Two Pointers
- Asked at: Amazon, Microsoft, Meta, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the head of a singly linked list sorted in non-decreasing order. Delete every node whose value appears more than once in the list, keeping only the values that occur exactly once, and return the head of the resulting list (still sorted).
Example 1
Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
Explanation: 3 and 4 each appear twice, so all their nodes go.
Example 2
Input: head = [1,1,1,2,3]
Output: [2,3]
Explanation: The run of 1s at the head is removed completely.
Example 3
Input: head = [7,7]
Output: []
Constraints
The number of nodes in the list is in the range [0, 300]-100 <= Node.val <= 100The list is sorted in non-decreasing order
Hints for Remove Duplicates from Sorted List II
Hint 1
In a sorted list, all copies of a value form one consecutive run. A value survives exactly when its run has length 1.
Hint 2
Keep
prev, the last node known to survive, and look at the run that starts atprev.next.Hint 3
If the run is longer than one node, skip all of it with
prev.next = <first node after the run>; otherwise advanceprev. A dummy node handles a duplicated head.
How to solve Remove Duplicates from Sorted List II
Examine the list run by run. A run of equal values of length one is kept; a longer run is cut out entirely by linking the last kept node past it.
Approach
- Create a dummy node before
headand setprev = dummy. - While
prev.nextexists, letcur = prev.next. - If
cur.nextexists and has the same value, advancecurto the last node of the run and setprev.next = cur.next(the whole run disappears;prevstays). - Otherwise the value is unique:
prev = prev.next. - Return
dummy.next.
Why it works
prev only ever moves onto a node whose run has length one, and every longer run is unlinked as a whole before prev looks past it. So exactly the unique values remain, in their original sorted order.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Unlike LC 83, the first copy is not kept — the whole run goes.
- After removing a run, do not advance
prev: the next run may also be duplicated. - The head itself may be part of a duplicated run; the dummy node covers that.
Reference solution
Python
from typing import Optional
def deleteDuplicates(head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0, head)
prev = dummy
while prev.next:
cur = prev.next
if cur.next and cur.next.val == cur.val:
while cur.next and cur.next.val == cur.val:
cur = cur.next
prev.next = cur.next
else:
prev = cur
return dummy.nextJava
public static ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0, head), prev = dummy;
while (prev.next != null) {
ListNode cur = prev.next;
if (cur.next != null && cur.next.val == cur.val) {
while (cur.next != null && cur.next.val == cur.val) cur = cur.next;
prev.next = cur.next;
} else {
prev = cur;
}
}
return dummy.next;
}C++
ListNode* deleteDuplicates(ListNode* head) {
ListNode dummy(0, head);
ListNode* prev = &dummy;
while (prev->next) {
ListNode* cur = prev->next;
if (cur->next && cur->next->val == cur->val) {
while (cur->next && cur->next->val == cur->val) cur = cur->next;
prev->next = cur->next;
} else {
prev = cur;
}
}
return dummy.next;
}JavaScript
var deleteDuplicates = function(head) {
var dummy = new ListNode(0, head), prev = dummy;
while (prev.next !== null) {
var cur = prev.next;
if (cur.next !== null && cur.next.val === cur.val) {
while (cur.next !== null && cur.next.val === cur.val) cur = cur.next;
prev.next = cur.next;
} else {
prev = cur;
}
}
return dummy.next;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 165 two pointers problems · the whole catalogue
Learn the technique: Two Pointers Technique