Remove Duplicates from Sorted List II

• Time : $O(n)$
• Space : $O(n)$

c++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
ListNode* Solution::deleteDuplicates(ListNode* A) {
    ListNode* dummy = new ListNode(INT_MIN);
    dummy->next = A;
    ListNode* runner = dummy;
    while(runner->next and runner->next->next) {
        if(runner->next->next->val == runner->next->val) {
            ListNode* move = runner->next;
            while(move and move->val == runner->next->val) move = move->next;
            runner->next = move;
        }
        else runner = runner->next;
    }
    return dummy->next;
}