Remove All Duplicates from Sorted List II — Dummy + Skip
Advertisement
Problem 225 · Remove Duplicates from Sorted List II
Difficulty: Medium · Pattern: Dummy Head + Skip Duplicates
Remove all nodes whose values appear more than once.
Solutions
# Python
def deleteDuplicates(head):
dummy = ListNode(0, head)
prev = dummy
while prev.next:
cur = prev.next
# Skip all nodes with same value
if cur.next and cur.val == cur.next.val:
while cur.next and cur.val == cur.next.val:
cur = cur.next
prev.next = cur.next # skip all with that value
else:
prev = prev.next
return dummy.next
// Java
public 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.val == cur.next.val) {
while (cur.next != null && cur.val == cur.next.val) cur = cur.next;
prev.next = cur.next;
} else prev = prev.next;
}
return dummy.next;
}
// C++
ListNode* deleteDuplicates(ListNode* head) {
ListNode dummy(0, head), *prev = &dummy;
while (prev->next) {
ListNode* cur = prev->next;
if (cur->next && cur->val == cur->next->val) {
while (cur->next && cur->val == cur->next->val) cur = cur->next;
prev->next = cur->next;
} else prev = prev->next;
}
return dummy.next;
}
Complexity
- Time: O(n)
- Space: O(1)
Advertisement