  # LeetCode - Remove Duplicates from Sorted List II

## Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii

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.
``````

### Explanation

#### Using Hash Map

We can use a simple hash map to solve the problem. We store the node value as the hash map key. The value of each key will be the number of times a key appears in the list.

We then iterate over this hash map and create a new list for keys that appear only once.

A C++ snippet of this logic will look as below:

``````ListNode* removeDuplicates(ListNode* head) {
map<int, int> map;

map<int, int> map;

}

ListNode* prev = new ListNode(0);

for(auto it: map) {
if(it.second == 1) {
ListNode* cur = new ListNode(it.first);
prev->next = cur;
prev = cur;
}
}
}``````

The time-complexity of the function is O(N), and the space complexity is O(N).

#### Using Sentinel

The Example 1 can be solved by using two pointers. Things become tricky for Example 2. We do come across these cases a lot when dealing with linked lists. To solve such kinds of issues, we use Sentinel Node. These nodes are used as pseudo head or tail to deal with edge cases like Example 2.

To solve this problem, we will use a sentinel head to ensure the situation deletes the list head never happens.

The input list is sorted, and we should compare the node value with its next node. We use a predecessor pointer that points to the last node before the sub-list of duplicates. Once the duplicate sub-list ends, we point predecessors next to the non-duplicate node.

Let's check the algorithm:

``````- set sentinel = ListNode(0)
set predecessor = sentinel

- loop while head != NULL
// if the sub-list is duplicate

// point predecessor's next to the non-duplicate node

- else
- set predecessor = predecessor->next
- end if

- end while

- return sentinel-next
``````

The time-complexity of this function is O(N), and the space complexity is O(1).

Let's check our solutions in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
ListNode* sentinel = new ListNode(0);
ListNode* predecessor = sentinel;

}

} else {
predecessor = predecessor->next;
}

}

return sentinel->next;
}
};``````

#### Golang solution

``````func deleteDuplicates(head *ListNode) *ListNode {
sentinel := &ListNode{
Val: 0,
}

predecessor := sentinel

}

} else {
predecessor = predecessor.Next
}

}

return sentinel.Next
}``````

#### Javascript solution

``````var deleteDuplicates = function(head) {
let sentinel = new ListNode(0, head);
let predecessor = sentinel;

}

} else {
predecessor = predecessor.next;
}

}

return sentinel.next;
};``````

#### Dry Run

Let's dry-run our algorithm to see how the solution works.

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

Step 1: ListNode* sentinel = new ListNode(0)

sentinel = [0, 1, 1, 1, 2, 3]

ListNode* predecessor = sentinel
predecessor = [1, 1, 1, 2, 3]

Step 2: loop while head != NULL
1 != NULL
true

1 != NULL && 1 == 1
true

predecessor = [2, 3]

sentinel = [0, 2, 3]

Step 3: loop while head != NULL
2 != NULL
true

2 != NULL && 2 == 3
false

else
predecessor = predecessor->next
predecessor = 

sentinel = [0, 2, 3]

Step 4: loop while head != NULL
3 != NULL
true

NULL != NULL
false

else
predecessor = predecessor->next
predecessor = NULL