82. Remove Duplicates from Sorted List II

1. Description

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 linked list sorted as well.

2. Example

Example 1

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

Example 2

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

3. Constraints

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

4. Solutions

Linked List

n is the number of nodes in head
Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode dummy;
        ListNode *write = &dummy, *read = head;
        while (read != nullptr) {
            int value = read->val, count = 0;
            while (read != nullptr && read->val == value) {
                ++count;
                read = read->next;
            }

            if (count == 1) {
                write->next = new ListNode(value);
                write = write->next;
            }
        }

        return dummy.next;
    }
};