# Remove Duplicates from Sorted List II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii)
Canonical: https://scaleengineer.com/dsa/problems/remove-duplicates-from-sorted-list-ii
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Linked List
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Google](https://scaleengineer.com/companies/google), [Microsoft](https://scaleengineer.com/companies/microsoft), [Tencent](https://scaleengineer.com/companies/tencent)
---
## Problem
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:**

![](https://assets.glich.co/dsa/remove-duplicates-from-sorted-list-ii/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/remove-duplicates-from-sorted-list-ii/image1.jpg) 

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

# Approaches
## Two-Pass with Hash Map
This approach involves two traversals of the linked list. The first traversal counts the frequency of each number and stores it in a hash map. The second traversal builds a new linked list, including only the nodes whose values have a frequency of one.
**Time:** O(N) · **Space:** O(K), where K is the number of distinct elements
**Pros:** Simple to understand and implement.; Separates the logic of counting and building, which can be easier to reason about.
**Cons:** Requires two passes over the list.; Uses O(K) extra space for the hash map, where K is the number of distinct elements.; It's not an in-place solution as it builds a completely new list.
### Explanation
We first iterate through the entire linked list to populate a hash map (or a frequency array since the value range is small) with the counts of each node value.
After counting, we create a new sentinel (dummy) node to simplify the construction of the result list. A `tail` pointer will track the end of this new list.
We then iterate through the original list again. For each node, we check its value's frequency in our hash map.
If the frequency is exactly 1, it means the node is unique. We create a new node with this value and append it to our result list, advancing the `tail` pointer.
Finally, we return the `next` of our sentinel node, which is the head of the new, filtered list.
```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }

        Map<Integer, Integer> counts = new HashMap<>();
        ListNode current = head;
        while (current != null) {
            counts.put(current.val, counts.getOrDefault(current.val, 0) + 1);
            current = current.next;
        }

        ListNode sentinel = new ListNode(0);
        ListNode tail = sentinel;

        current = head;
        while (current != null) {
            if (counts.get(current.val) == 1) {
                tail.next = new ListNode(current.val);
                tail = tail.next;
            }
            current = current.next;
        }

        return sentinel.next;
    }
}
```
### Algorithm
- Create a `HashMap` to store the frequency of each number.
- Traverse the linked list from `head` to `tail`, and for each node, update its value's count in the hash map.
- Initialize a `sentinel` node and a `tail` pointer pointing to it. This will be the start of our new list.
- Traverse the original linked list again.
- For each node, look up its value in the hash map.
- If the count is 1, create a new node with this value and append it to the list pointed to by `tail`. Move `tail` to this new node.
- Return `sentinel.next`.

## Recursive Approach
This approach solves the problem recursively. The function processes the list starting from the head. It decides whether to keep the head node based on whether it's a duplicate. If it is, it skips the entire sequence of duplicates and recursively calls itself on the rest of the list. If not, it keeps the head and recursively processes the remainder of the list.
**Time:** O(N) · **Space:** O(N)
**Pros:** Code can be very concise and elegant.; Follows a natural divide-and-conquer pattern.
**Cons:** Can lead to a stack overflow for very long lists due to deep recursion.; Space complexity is O(N) in the worst case because of the recursion call stack.
### Explanation
The base case for the recursion is an empty list (`head == null`), in which case we return `null`.
We check if the current `head` node is part of a duplicate sequence by comparing its value with the next node's value (`head.next != null && head.val == head.next.val`).
If it is a duplicate, we must discard all nodes with this value. We use a loop to advance a pointer past all nodes with the same value. Then, we make a recursive call with the first node that has a different value. The result of this recursive call is the result for the current level.
If the `head` is not a duplicate, we know it must be included in the final list. So, we keep it and recursively call the function on `head.next`. The result of this sub-problem becomes the new `head.next`. We then return the `head`.
```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // Base case: empty list or a single node list
        if (head == null || head.next == null) {
            return head;
        }

        // Check if the head is part of a duplicate sequence
        if (head.val == head.next.val) {
            // Skip all nodes with the same value as head
            ListNode current = head;
            while (current != null && current.val == head.val) {
                current = current.next;
            }
            // Recursively call on the rest of the list
            return deleteDuplicates(current);
        } else {
            // Head is not a duplicate, keep it.
            // Recursively call on the rest of the list and connect it
            head.next = deleteDuplicates(head.next);
            return head;
        }
    }
}
```
### Algorithm
- Define a recursive function `deleteDuplicates(node)`.
- **Base Case**: If `node` is `null`, return `null`.
- Check if `node.next` exists and `node.val == node.next.val`.
- **If true (duplicate found)**:
    - Create a temporary pointer `temp` and move it forward as long as the nodes have the same value as `node`.
    - Return the result of `deleteDuplicates(temp)`.
- **If false (node is unique)**:
    - The `node` is part of the result. Recursively process the rest of the list by calling `deleteDuplicates(node.next)`.
    - Set `node.next` to the result of the recursive call.
    - Return `node`.

## One-Pass Iterative Approach
This is the most optimal approach, using a single pass and constant extra space. It uses a `sentinel` node and a `predecessor` pointer to rebuild the list in-place. The `predecessor` points to the last node in the result list that is guaranteed to be unique.
**Time:** O(N) · **Space:** O(1)
**Pros:** Most efficient solution with O(1) space complexity.; Modifies the list in-place.; Handles all edge cases gracefully, especially with the use of a sentinel node.
**Cons:** The pointer manipulation can be slightly more complex to reason about compared to other approaches.
### Explanation
We introduce a `sentinel` (or `dummy`) node, which points to the original `head`. This helps manage edge cases, such as when the head of the list is a duplicate and needs to be removed.
We use a `pred` (predecessor) pointer, initialized to the `sentinel`. This pointer will always point to the node just before a potential sequence of duplicates.
We iterate through the list using a `head` pointer.
In each step, we check if `head` is the beginning of a duplicate sequence (i.e., `head.next != null && head.val == head.next.val`).
If it is, we enter an inner loop to skip all nodes that are part of this duplicate sequence. We keep moving `head` forward until it points to a node with a different value. After the inner loop, `head` is the last node of the duplicate sequence. We then link `pred.next` to `head.next`, effectively removing the entire duplicate sequence.
If `head` is not the start of a duplicate sequence, it means this node is unique and should be kept. We simply move our `pred` pointer forward to `pred.next`.
In both cases, we advance `head` to the next node to continue the process.
Finally, we return `sentinel.next`.
```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // Use a sentinel node to handle deletion of the head node
        ListNode sentinel = new ListNode(0, head);

        // Predecessor is the last node before the sublist of duplicates
        ListNode pred = sentinel;
        
        while (head != null) {
            // If it's a beginning of duplicates sublist
            // i.e. head.next is not null and its value is the same as head
            if (head.next != null && head.val == head.next.val) {
                // Move till the end of duplicates sublist
                while (head.next != null && head.val == head.next.val) {
                    head = head.next;
                }
                // Skip all duplicates
                pred.next = head.next;
            // Otherwise, move predecessor
            } else {
                pred = pred.next;
            }
            
            // Move forward
            head = head.next;
        }
        return sentinel.next;
    }
}
```
### Algorithm
- Create a `sentinel` node and set its `next` to the original `head`.
- Initialize a `pred` (predecessor) pointer to the `sentinel`.
- Initialize a `current` pointer to `head`.
- Loop while `current` is not `null`:
    - Check if `current` is the start of a duplicate sequence (`current.next != null && current.val == current.next.val`).
    - **If true (duplicate found)**:
        - Move `current` forward until it's the last node in the duplicate sequence.
        - Update `pred.next` to point to `current.next`, effectively skipping the entire duplicate sequence.
    - **If false (node is unique)**:
        - Move `pred` to the next node (`pred = pred.next`).
    - Move `current` to the next node (`current = current.next`).
- Return `sentinel.next`.

# Solutions
### CSharp

```csharp
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode DeleteDuplicates ( ListNode head ) { ListNode dummy = new ListNode ( 0 , head ); ListNode pre = dummy ; ListNode cur = head ; while ( cur != null ) { while ( cur . next != null && cur . next . val == cur . val ) { cur = cur . next ; } if ( pre . next == cur ) { pre = cur ; } else { pre . next = cur . next ; } cur = cur . next ; } return dummy . next ; } }
```

### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode deleteDuplicates ( ListNode head ) { ListNode dummy = new ListNode ( 0 , head ); ListNode pre = dummy ; ListNode cur = head ; while ( cur != null ) { while ( cur . next != null && cur . next . val == cur . val ) { cur = cur . next ; } if ( pre . next == cur ) { pre = cur ; } else { pre . next = cur . next ; } cur = cur . next ; } return dummy . next ; } }
```

### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var deleteDuplicates = function ( head ) { const dummy = new ListNode ( 0 , head ); let pre = dummy ; let cur = head ; while ( cur ) { while ( cur . next && cur . val === cur . next . val ) { cur = cur . next ; } if ( pre . next === cur ) { pre = cur ; } else { pre . next = cur . next ; } cur = cur . next ; } return dummy . next ; };
```

### CPP

```cpp
/** * 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 ( 0 , head ); ListNode * pre = dummy ; ListNode * cur = head ; while ( cur ) { while ( cur -> next && cur -> next -> val == cur -> val ) { cur = cur -> next ; } if ( pre -> next == cur ) { pre = cur ; } else { pre -> next = cur -> next ; } cur = cur -> next ; } return dummy -> next ; } };
```

### Python

```python
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def deleteDuplicates ( self , head : Optional [ ListNode ]) -> Optional [ ListNode ]: dummy = pre = ListNode ( next = head ) cur = head while cur : while cur . next and cur . next . val == cur . val : cur = cur . next if pre . next == cur : pre = cur else : pre . next = cur . next cur = cur . next return dummy . next
```