# LeetCode 82: Remove Duplicates from Sorted List II

## Problem Restatement

We are given the head of a sorted linked list.

We need to delete every node whose value appears more than once.

This is stronger than keeping one copy.

If a value appears two or more times, all nodes with that value must be removed.

For example:

```python
1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
```

The values `3` and `4` are duplicated, so all `3` nodes and all `4` nodes are removed.

The result is:

```python
1 -> 2 -> 5
```

The official statement says to delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. The returned list should remain sorted. Constraints include `0 <= number of nodes <= 300`, `-100 <= Node.val <= 100`, and the list is sorted in ascending order.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Head of a sorted linked list |
| Output | Head of the modified linked list |
| Remove rule | Remove every value that appears more than once |
| Keep rule | Keep only values that appear exactly once |
| Order | The result remains sorted |

Function shape:

```python
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        ...
```

## Examples

Example 1:

```python
head = [1, 2, 3, 3, 4, 4, 5]
```

The values `3` and `4` appear more than once.

Remove all nodes with those values.

Answer:

```python
[1, 2, 5]
```

Example 2:

```python
head = [1, 1, 1, 2, 3]
```

The value `1` appears three times.

Remove all `1` nodes.

Answer:

```python
[2, 3]
```

Example 3:

```python
head = [1, 1]
```

The value `1` appears more than once.

Answer:

```python
[]
```

## First Thought: Count Frequencies

One simple way is to make two passes.

First pass:

```python
count[value] += 1
```

Second pass:

```python
keep only nodes where count[value] == 1
```

This works, but it uses extra space.

Because the linked list is sorted, duplicate values appear in consecutive groups. We can remove duplicate groups in one pass with constant extra space.

## Key Insight

Since the list is sorted, equal values are adjacent.

So the list can be viewed as groups:

```python
1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
```

Groups:

```python
[1], [2], [3, 3], [4, 4], [5]
```

We keep groups of size `1`.

We remove groups of size greater than `1`.

The hard part is deleting duplicates at the head.

For example:

```python
1 -> 1 -> 1 -> 2 -> 3
```

The real head must change from `1` to `2`.

A dummy node solves this cleanly.

```python
dummy -> 1 -> 1 -> 1 -> 2 -> 3
```

The dummy node gives us a stable node before the real head, so we can rewire `dummy.next` if the first group must be removed.

## Algorithm

Create a dummy node before `head`.

Use two pointers:

| Pointer | Meaning |
|---|---|
| `prev` | Last node before the current group |
| `cur` | Current node being inspected |

Start:

```python
dummy.next = head
prev = dummy
cur = head
```

Then scan the list.

For each group:

1. Check whether `cur` has the same value as `cur.next`.
2. If yes, move `cur` until the last node of that duplicate group.
3. Remove the whole group by setting:

```python
prev.next = cur.next
```

4. If no duplicate was found, move `prev` forward:

```python
prev = prev.next
```

5. Move `cur` forward.

At the end, return:

```python
dummy.next
```

## Walkthrough

Use:

```python
1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
```

Add dummy:

```python
dummy -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
```

Start:

```python
prev = dummy
cur = 1
```

Value `1` has no duplicate.

Move `prev` to `1`.

```python
dummy -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
        prev
             cur = 2
```

Value `2` has no duplicate.

Move `prev` to `2`.

```python
dummy -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
             prev
                  cur = 3
```

Value `3` has a duplicate.

Move `cur` to the last `3`.

Then remove the whole group:

```python
prev.next = cur.next
```

Now the list becomes:

```python
dummy -> 1 -> 2 -> 4 -> 4 -> 5
```

`prev` stays at `2`.

Now `cur` moves to `4`.

Value `4` has a duplicate.

Skip all `4` nodes and rewire:

```python
prev.next = cur.next
```

Now the list becomes:

```python
dummy -> 1 -> 2 -> 5
```

Value `5` has no duplicate, so it stays.

Return:

```python
dummy.next
```

which is:

```python
1 -> 2 -> 5
```

## Correctness

The list is sorted, so all nodes with the same value appear in one consecutive group.

The algorithm processes one such group at a time.

If the current group has size `1`, then its value appears exactly once in the original list. The algorithm keeps it by moving `prev` forward to that node.

If the current group has size greater than `1`, then its value is duplicated. The algorithm moves `cur` to the last node of that group, then connects `prev.next` to the node after the group. This removes every node with that duplicated value.

The dummy node ensures the same logic works when the first group is removed. In that case, `prev` is the dummy node, and rewiring `prev.next` changes the returned head.

Because every group is either kept exactly once or removed completely, and because all groups are processed in order, the final list contains exactly the values that appeared once in the original sorted list.

Therefore, the algorithm is correct.

## Complexity

Let:

```python
n = number of nodes
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is visited at most a constant number of times |
| Space | `O(1)` | Only a few pointers are used |

## Implementation

```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 = ListNode(0, head)
        prev = dummy
        cur = head

        while cur:
            has_duplicate = False

            while cur.next and cur.val == cur.next.val:
                has_duplicate = True
                cur = cur.next

            if has_duplicate:
                prev.next = cur.next
            else:
                prev = prev.next

            cur = cur.next

        return dummy.next
```

## Code Explanation

Create a dummy node before the list:

```python
dummy = ListNode(0, head)
```

Set `prev` to the node before the current group:

```python
prev = dummy
```

Set `cur` to the current group start:

```python
cur = head
```

For every group, we first assume no duplicate has been found:

```python
has_duplicate = False
```

Then we walk through all nodes with the same value:

```python
while cur.next and cur.val == cur.next.val:
    has_duplicate = True
    cur = cur.next
```

If a duplicate group was found, remove the whole group:

```python
if has_duplicate:
    prev.next = cur.next
```

`prev` does not move, because the next group may also need to be removed.

If the group was unique, keep it and advance `prev`:

```python
else:
    prev = prev.next
```

Then move to the next group:

```python
cur = cur.next
```

Finally, return the real head after all rewiring:

```python
return dummy.next
```

## Testing

The helpers below make local testing easier.

```python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    cur = dummy

    for value in values:
        cur.next = ListNode(value)
        cur = cur.next

    return dummy.next

def to_list(head):
    values = []

    while head:
        values.append(head.val)
        head = head.next

    return values

def check(values, expected):
    s = Solution()
    head = build_list(values)
    result = s.deleteDuplicates(head)
    assert to_list(result) == expected

def run_tests():
    check([1, 2, 3, 3, 4, 4, 5], [1, 2, 5])
    check([1, 1, 1, 2, 3], [2, 3])
    check([1, 1], [])
    check([1], [1])
    check([], [])
    check([1, 2, 2], [1])
    check([1, 1, 2], [2])
    check([1, 2, 3], [1, 2, 3])

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 2, 3, 3, 4, 4, 5]` | Main example |
| `[1, 1, 1, 2, 3]` | Duplicates at the head |
| `[1, 1]` | Entire list removed |
| `[1]` | Single unique node |
| `[]` | Empty list |
| `[1, 2, 2]` | Duplicates at the tail |
| `[1, 1, 2]` | Head changes |
| `[1, 2, 3]` | No duplicates |