82. Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

Input: 1->1->1->2->3
Output: 2->3

// Iteration
ListNode* deleteDuplicates(ListNode* head) { // time: O(n); space: O(1)
    if (!head || !head->next) return head;
    ListNode* dummy = new ListNode(INT_MIN);
    dummy->next = head;
    ListNode *pre = dummy, *cur = head;
    while (cur) {
        if (cur->next && cur->val == cur->next->val) {
            int curVal = cur->val;
            while (cur && cur->val == curVal) {
                ListNode* nodeToDel = cur;
                cur = cur->next;
                delete nodeToDel;
            }
            pre->next = cur;
        } else {
            pre = cur;
            cur = cur->next;
        }
    }
    ListNode* res = dummy->next;
    delete dummy;
    return res;
}

// Recursion
ListNode* deleteDuplicates(ListNode* head) { // time: O(n); space: O(n)
    if (!head || !head->next) return head;
    int curVal = head->val;
    ListNode* p = head->next;
    if (p->val == curVal) {
        while (p && p->val == curVal) {
            ListNode* nodeToDel = p;
            p = p->next;
            delete nodeToDel;
        }
        return deleteDuplicates(p);
    } else {
        head->next = deleteDuplicates(p);
        return head;
    }
}