82. Remove Duplicates from Sorted List II

2020, Dec 05 One min read

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

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

Example 2

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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode dummy(0, head);
        ListNode *tail = &dummy;

        for (auto iter = head; iter != nullptr;) {
            if (iter->next == nullptr || iter->next->val != iter->val) {
                tail->next = iter;
                tail = iter;
                iter = iter->next;
            } else {
                int value = iter->val;
                while (iter != nullptr && iter->val == value) {
                    iter = iter->next;
                }
            }
        }

        tail->next = nullptr;
        return dummy.next;
    }
};

Search

Tags