Day 5 - Remove Duplicates from Sorted List II
Tags: leetcode, python
Published: 2021-01-05 22:00:18

## The 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:__

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/rgr0pmxhckuu4pgzho01.jpg)

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

__Example 2:__

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/4tb5is5gsm4hl42kmjz6.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.

## My Tests

```python
import pytest
from typing import List
from .util import ListNode, toListNode, toList
from .Day5 import Solution

s = Solution()


@pytest.mark.parametrize(
    "input,expected",
    [
        ([1, 2, 3, 3, 4, 4, 5], [1, 2, 5]),
        ([1, 2, 3, 3, 3, 4, 4, 5], [1, 2, 5]),
        ([1, 1, 1, 2, 3], [2, 3]),
        ([2, 3, 4], [2, 3, 4]),
        ([1, 1], []),
        ([0], [0]),
        ([], []),
        ([1, 1, 2, 2], []),
    ],
)
def test_remove_duplicates(input, expected):
    assert toList(s.deleteDuplicates(toListNode(input))) == expected
```

## My Solution

```python
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        holder = ListNode(0, head)
        dummy_head = holder
        next_node = head

        while next_node:
            if next_node.next is not None and next_node.next.val == next_node.val:
                while (
                    next_node.next is not None and next_node.val == next_node.next.val
                ):
                    next_node = next_node.next
                dummy_head.next = next_node.next
            else:
                dummy_head = dummy_head.next
            next_node = next_node.next

        return holder.next
```

## Analysis

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/8cde804hvq1bvkrgqg9r.png)

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/82tsadb1ukf3ac4bnua0.png)


## My Commentary

This was another one I thought would be super easy but I got confused a bunch of times trying to figure out the pointers. I even messed up my first attempt because I didn't read the question correctly and thought I just had to remove duplicates without removing all instances of a number that had a match. 

I did think initially I would need to keep pointers for the current head and the next list item. I assumed all I would have to do is increment the `next` pointer while there was a match. As soon as we didn't have a match, bump the `head.next` to `next`. Of course, we would then need another pointer for `head.next` to carry on. I ended up with a bunch of if statements and a mess of code.  

It took me a while to realise the easiest thing to do is create a `holder` pointer that would easily allow me to increment `head` (when there are duplicates at the beginning) and then we can set up a dummy head pointer as well as a `next_node` pointer.

So then we check for duplicates, increment the `next_node` pointer for all those duplicates. Then we push the `dummy_head` pointer past the duplicates which we can safely do because we kept the original head in the `holder`.

If we don't see a duplicate we just increment the `dummy_head` pointer to the next node in 
the list. 

I feel like if I got this in an interview yesterday I would have been in trouble even though the solution seems so obvious now.