# Remove Duplicates from Sorted List
**Difficulty:** EASY
[External](https://leetcode.com/problems/remove-duplicates-from-sorted-list)
Canonical: https://scaleengineer.com/dsa/problems/remove-duplicates-from-sorted-list
**Data structures:** Linked List
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Revolut](https://scaleengineer.com/companies/revolut)
---
## Problem
Given the `head` of a sorted linked list, _delete all duplicates such that each element appears only once_. Return _the linked list **sorted** as well_.

**Example 1:**

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

**Input:** head = [1,1,2]
**Output:** [1,2]

**Example 2:**

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

**Input:** head = [1,1,2,3,3]
**Output:** [1,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
## Using a Hash Set
This approach involves iterating through the linked list and using an auxiliary data structure, a hash set, to keep track of the elements that have already been added to the result list. A new list is constructed containing only the unique elements.
**Time:** O(N) · **Space:** O(K), where K is the number of unique elements. In the worst case, this is O(N).
**Pros:** Conceptually simple.; Works for unsorted lists as well, making it a more general solution for duplicate removal.
**Cons:** Uses extra space for the hash set, which is not optimal for this specific problem where the list is sorted.; Requires building a new list, which consumes additional memory and can be slower than an in-place modification.
### Explanation
We can solve this problem by creating a new linked list that will only contain the unique elements from the original list.

To do this, we'll use a `HashSet` to store the values of the nodes we've already encountered. We'll iterate through the original list, and for each node, we check if its value is already in our hash set.

- If the value is not in the set, it's the first time we're seeing this element. We add it to our new list and also add its value to the hash set.
- If the value is already in the set, it's a duplicate, so we simply skip it and move to the next node in the original list.

We use a `dummy` head node to simplify the process of building the new 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; }
 * }
 */
import java.util.HashSet;
import java.util.Set;

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }

        Set<Integer> seen = new HashSet<>();
        ListNode dummy = new ListNode(0); // Dummy head for the new list
        ListNode newTail = dummy;
        ListNode current = head;

        while (current != null) {
            if (!seen.contains(current.val)) {
                seen.add(current.val);
                newTail.next = new ListNode(current.val);
                newTail = newTail.next;
            }
            current = current.next;
        }

        return dummy.next;
    }
}
```
### Algorithm
- Initialize an empty `HashSet` called `seen`.
- Create a `dummy` node to act as the starting point for the new, de-duplicated list.
- Create a `newTail` pointer, initially pointing to `dummy`.
- Initialize a `current` pointer to the `head` of the input list.
- Iterate through the input list with the `current` pointer until it becomes `null`.
- Inside the loop, check if `current.val` exists in the `seen` set.
- If `current.val` is not in `seen`, add it to the set, create a new node with this value, append it to the new list (`newTail.next`), and move `newTail` to this new node.
- If `current.val` is already in `seen`, do nothing.
- Move `current` to the next node in the original list.
- After the loop, return `dummy.next`, which is the head of the new list.

## One-Pointer Iterative Approach
This is the most efficient approach, which leverages the fact that the input list is sorted. Since it's sorted, any duplicate elements will be adjacent to each other. We can traverse the list and remove duplicates in-place.
**Time:** O(N) · **Space:** O(1)
**Pros:** Optimal space complexity of O(1) as it modifies the list in-place.; Optimal time complexity of O(N) with a single pass.; The code is concise and easy to understand.
**Cons:** This approach only works because the input list is guaranteed to be sorted.
### Explanation
We can solve this problem with a single pass and without using any extra space. The key insight is that because the list is sorted, we can just compare each node with its immediate successor.

We'll use a pointer, let's call it `current`, that starts at the `head` of the list. We then look at the next node, `current.next`.

- If `current.val` is the same as `current.next.val`, we know `current.next` is a duplicate. To remove it, we can simply bypass it by setting `current.next` to `current.next.next`. We don't advance `current` yet, because the new `current.next` could also be a duplicate (e.g., in a list like `1 -> 1 -> 1`).
- If `current.val` is different from `current.next.val`, it means there's no duplicate, so we can safely move `current` one step forward to `current.next`.

We repeat this process until `current` or `current.next` becomes `null`.

```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) {
        // Start with the head of the list
        ListNode current = head;

        // Traverse the list as long as the current node and the next node are not null
        while (current != null && current.next != null) {
            // If the current node's value is the same as the next node's value
            if (current.val == current.next.val) {
                // Skip the duplicate node
                current.next = current.next.next;
            } else {
                // Move to the next node
                current = current.next;
            }
        }
        
        // Return the modified head of the list
        return head;
    }
}
```
### Algorithm
- Initialize a pointer `current` to the `head` of the list.
- Handle the edge case where the list is empty or has only one node by returning `head`.
- Loop as long as `current` and `current.next` are not `null`.
- Inside the loop, compare `current.val` with `current.next.val`.
- If they are equal, it's a duplicate. Modify the `next` pointer of the `current` node to skip the duplicate: `current.next = current.next.next`.
- If they are not equal, the next element is unique. Move the `current` pointer forward: `current = current.next`.
- After the loop terminates, return the original `head`, which now points to the de-duplicated list.

# Solutions
### 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 cur = head ; while ( cur != null && cur . next != null ) { if ( cur . val == cur . next . val ) { cur . next = cur . next . next ; } else { cur = cur . next ; } } return head ; } }
```

### 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 cur = head ; while ( cur != null && cur . next != null ) { if ( cur . val == cur . next . val ) { cur . next = cur . next . next ; } else { cur = cur . next ; } } return head ; } }
```

### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var deleteDuplicates = function ( head ) { let cur = head ; while ( cur && cur . next ) { if ( cur . next . val === cur . val ) { cur . next = cur . next . next ; } else { cur = cur . next ; } } return head ; };
```

### 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 * cur = head ; while ( cur != nullptr && cur -> next != nullptr ) { if ( cur -> val == cur -> next -> val ) { cur -> next = cur -> next -> next ; } else { cur = cur -> next ; } } return head ; } };
```

### 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 ]: cur = head while cur and cur . next : if cur . val == cur . next . val : cur . next = cur . next . next else : cur = cur . next return head
```