Remove Duplicates from Sorted List II
Remove Duplicates from Sorted List II is a medium linked list problem solved with the dummy node pattern pattern.
The best approach, optimal (dummy node, skip runs), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (count values) up.
Problem
Given a sorted linked list, delete every node whose value appears more than once, keeping only values that were distinct in the original list. Return the sorted result.
Examples
Example 1
- Input
head = [1, 2, 3, 3, 4, 4, 5]- Output
[1, 2, 5]- Why
- Every value that repeats is removed completely.
Example 2
- Input
head = [1, 1, 1, 2, 3]- Output
[2, 3]
Constraints
- The list has
0to300nodes, sorted in non-decreasing order.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (count values) | O(n) | O(n) |
| Optimal (dummy node, skip runs) | O(n) | O(1) |
1Brute force (count values)
O(n)O(n)Count each value in a map, then rebuild the list with only values whose count is 1.
- Count values.
- Link together nodes whose value count is 1.
class Solution {
public ListNode deleteDuplicates(ListNode head) {
Map<Integer, Integer> count = new HashMap<>();
for (ListNode p = head; p != null; p = p.next) count.merge(p.val, 1, Integer::sum);
ListNode dummy = new ListNode(), tail = dummy;
for (ListNode p = head; p != null; p = p.next) {
if (count.get(p.val) == 1) { tail.next = p; tail = p; }
}
tail.next = null;
return dummy.next;
}
}class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
count = {}
p = head
while p:
count[p.val] = count.get(p.val, 0) + 1
p = p.next
dummy = ListNode()
tail = dummy
p = head
while p:
if count[p.val] == 1:
tail.next = p
tail = p
p = p.next
tail.next = None
return dummy.nextclass Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
unordered_map<int, int> count;
for (ListNode* p = head; p != nullptr; p = p->next) count[p->val]++;
ListNode* dummy = new ListNode();
ListNode* tail = dummy;
for (ListNode* p = head; p != nullptr; p = p->next) {
if (count[p->val] == 1) { tail->next = p; tail = p; }
}
tail->next = nullptr;
return dummy->next;
}
};function deleteDuplicates(head) {
const count = new Map();
for (let p = head; p !== null; p = p.next) count.set(p.val, (count.get(p.val) || 0) + 1);
const dummy = new ListNode();
let tail = dummy;
for (let p = head; p !== null; p = p.next) {
if (count.get(p.val) === 1) { tail.next = p; tail = p; }
}
tail.next = null;
return dummy.next;
}2Optimal (dummy node, skip runs)
O(n)O(1)prev stays on the last kept node. If the node after prev starts a run of equal values, skip the whole run by linking prev past it. Otherwise move prev forward.
- prev = dummy; cur = head.
- If cur.next has the same value, advance cur to the end of the run and set prev.next = cur.next.
- Else prev = prev.next. Then cur = cur.next.
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0, head), prev = dummy, cur = head;
while (cur != null) {
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 = prev.next;
}
cur = cur.next;
}
return dummy.next;
}
}class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0, head)
prev, cur = dummy, head
while cur:
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 = prev.next
cur = cur.next
return dummy.nextclass Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* dummy = new ListNode(0, head);
ListNode* prev = dummy;
ListNode* cur = head;
while (cur != nullptr) {
if (cur->next != nullptr && cur->next->val == cur->val) {
while (cur->next != nullptr && cur->next->val == cur->val) cur = cur->next;
prev->next = cur->next;
} else {
prev = prev->next;
}
cur = cur->next;
}
return dummy->next;
}
};function deleteDuplicates(head) {
const dummy = new ListNode(0, head);
let prev = dummy, cur = head;
while (cur !== null) {
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 = prev.next;
}
cur = cur.next;
}
return dummy.next;
}Edge cases to test
- Duplicates at the head
- The whole list is duplicates
- Duplicates at the tail
Hints
Hint 1
prev should point at the last node you know is unique. A dummy node covers duplicates at the head.
FAQ
What is the best time complexity for Remove Duplicates from Sorted List II?
Optimal (dummy node, skip runs) runs in O(n) time and O(1) extra space.
Which pattern does Remove Duplicates from Sorted List II use?
It is a linked list problem that uses the dummy node pattern pattern. Other problems with the same pattern: Remove Linked List Elements, Delete Nodes From Linked List Present in Array, Merge Two Sorted Lists.
Is there a brute force solution for Remove Duplicates from Sorted List II?
Yes. Brute force (count values) takes O(n) time and O(n) space. Count each value in a map, then rebuild the list with only values whose count is 1.
Which edge cases should I test for Remove Duplicates from Sorted List II?
Duplicates at the head; The whole list is duplicates; Duplicates at the tail.