Remove All Duplicates from Sorted List II — Dummy + Skip

Sanjeev SharmaSanjeev Sharma
1 min read

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

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro