# LeetCode 83: Remove Duplicates from Sorted List

## Problem Restatement

We are given the head of a sorted linked list.

We need to delete duplicate values so that each value appears only once.

Unlike LeetCode 82, we do not remove all copies of a duplicated value. We keep one copy.

For example:

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

becomes:

```python
1 -> 2
```

The official statement says to delete duplicates so that each element appears only once, then return the sorted linked list. The constraints are `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 | Keep one node for each value |
| Order | The list remains sorted |
| Extra memory | We can solve it with `O(1)` extra space |

Function shape:

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

## Examples

Example 1:

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

The value `1` appears twice.

Keep one `1`.

Answer:

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

Example 2:

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

The value `1` appears twice, and the value `3` appears twice.

Keep one copy of each.

Answer:

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

Example 3:

```python
head = []
```

There are no nodes.

Answer:

```python
[]
```

## First Thought: Use a Set

A common idea is to store values we have already seen.

While walking through the list, if a value already exists in the set, remove that node.

This works for many duplicate-removal problems, but here we can do better.

The list is sorted. That means duplicate values are always adjacent.

So we do not need a set.

## Key Insight

Because the list is sorted, equal values appear next to each other.

Example:

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

The duplicates form consecutive groups:

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

To keep one copy of each value, we only need to compare a node with its next node.

If:

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

then `cur.next` is a duplicate and should be skipped.

We remove it by rewiring:

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

If the values are different, then `cur` is the last copy of its value, so we can move forward.

## Algorithm

Use one pointer:

```python
cur = head
```

While both `cur` and `cur.next` exist:

1. If `cur.val == cur.next.val`, remove `cur.next`.
2. Otherwise, move `cur` forward.
3. Return `head`.

The important detail is that we do not move `cur` after removing a duplicate.

For example:

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

After removing the second `1`, the list becomes:

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

The current node is still `1`, and the next node is still a duplicate. So we must check again.

## Walkthrough

Use:

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

Start:

```python
cur = first 1
```

Compare `cur` with `cur.next`:

```python
1 == 1
```

The next node is a duplicate, so skip it:

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

The list becomes:

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

Now compare:

```python
1 != 2
```

Move `cur` to `2`.

Compare:

```python
2 != 3
```

Move `cur` to `3`.

Compare:

```python
3 == 3
```

Skip the duplicate `3`.

The list becomes:

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

Now `cur.next` is `None`, so stop.

Return the original head.

## Correctness

The algorithm keeps the first node of each value group.

Since the list is sorted, all duplicate copies of a value appear immediately after the first copy.

When `cur.val == cur.next.val`, `cur.next` is an extra copy of the same value. Rewiring `cur.next = cur.next.next` removes that duplicate while keeping one copy at `cur`.

When `cur.val != cur.next.val`, there are no more copies of `cur.val` after `cur`, because any equal values would have to be adjacent in a sorted list. Therefore, it is safe to move `cur` forward.

The loop continues until every adjacent pair has been checked or removed. At the end, no two adjacent nodes have the same value. Since the list is sorted, that means no value appears more than once.

Therefore, the returned list contains each original value exactly once.

## Complexity

Let:

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each duplicate removal or pointer move advances through the list |
| Space | `O(1)` | Only one pointer is 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]:
        cur = head

        while cur and cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next

        return head
```

## Code Explanation

Start at the head:

```python
cur = head
```

The loop needs both the current node and the next node:

```python
while cur and cur.next:
```

If the next node has the same value, skip it:

```python
if cur.val == cur.next.val:
    cur.next = cur.next.next
```

We do not move `cur` in this case, because there may be more duplicates after the removed node.

If the next value is different, move forward:

```python
else:
    cur = cur.next
```

Finally, return the original head:

```python
return head
```

This works even when `head` is `None`.

## Testing

```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, 1, 2], [1, 2])
    check([1, 1, 2, 3, 3], [1, 2, 3])
    check([], [])
    check([1], [1])
    check([1, 1, 1], [1])
    check([1, 2, 3], [1, 2, 3])
    check([-3, -3, -1, 0, 0, 2], [-3, -1, 0, 2])

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 1, 2]` | Main small duplicate case |
| `[1, 1, 2, 3, 3]` | Duplicates at head and tail |
| `[]` | Empty list |
| `[1]` | Single node |
| `[1, 1, 1]` | Many copies collapse to one |
| `[1, 2, 3]` | No duplicates |
| Negative and zero values | Confirms values are compared normally |