82 - Remove Duplicates from Sorted List II

Problem

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

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Input: head = [1,1,1,2,3]
Output: [2,3]

Constraints:

• The number of nodes is in the range [0, 300]
• -100 <= Node.val <= 100
• The list is sorted in ascending order

Approach

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode dummy(0, head);
        ListNode* prev = &dummy;
        ListNode* curr = head;
        while (curr) {
            while (curr->next && curr->val == curr->next->val) {
                curr = curr->next;
            }
            if (prev->next == curr) {
                prev = curr;
            } else {
                prev->next = curr->next;
            }
            curr = curr->next;
        }
        return dummy.next;
    }
};

[1,2,3,3,4,4,5]

prev=dummy curr=1   no move   keep  -> prev=1
prev=1     curr=2   no move   keep  -> prev=2
prev=2     curr=3a  -> 3b     drop  -> 2->4a
prev=2     curr=4a  -> 4b     drop  -> 2->5
prev=2     curr=5   no move   keep  -> prev=5
[1,2,5]

• time: O(n) - each node is compared with its neighbour once
• space: O(1) - two pointers and one stack node