Leetcode Study Day 30

Remove Duplicates from Sorted List II

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 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]
 

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.

My solution

My solution is create two nodes to track which element I should delete, one is called prev, the other is called current. I also use a set to store the elements that I have seen. If the current element is already in the set, then my prev node should point to the next node of current node. Otherwise, I will add the current element to the set and update the prev node to the current node. The method of updating prev node is to check whether the next node of current node is in the set. If it is in the set, then we should not update the prev node. Or we should update the prev node to the current node.

/**
 * 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 = new ListNode();
        ListNode* current = head;
        dummy -> next = current;
        ListNode* prev = dummy;
        unordered_set <int> listSet;
        while(current){
            // if it is already stored in the set
            if (listSet.find(current->val) != listSet.end()){
                prev->next = current -> next;
                current = current->next;
            }
            else{
                listSet.insert(current->val);
                current = current -> next;
                // update the prev node
                if(current){
                    if(listSet.find(current->val) == listSet.end()){
                        prev = prev->next;
                    }
                }
            }

        }
        return dummy -> next;
    }
};