[LeetCode Road] Remove Duplicates from Sorted List II - Solution/C++

82. Remove Duplicates from Sorted List II

Question:

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.

Example:

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 in the list is in the range [0, 300].

-100 <= Node.val <= 100

The list is guaranteed to be sorted in ascending order.

Source code

Version 1

Idea:
At the first while loop, it ensures no nullptr in next two pointers. Then, check the current value whether it is the same as the next value. If it is duplicate, store this value and compare with the next value until different value.

Time complexity: O(n)
Space complexity: O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        tail->next = head;
        while(tail->next && tail->next->next){
            if(tail->next->val == tail->next->next->val){
                int value = tail->next->val;
                while(tail->next && tail->next->val == value){
                    tail->next = tail->next->next;
                }
            }else{
                tail = tail->next;
            }
        }
        return dummy.next;
    }
};