# Remove Duplicates from Sorted List II

##### January 14, 2024

## Problem #

Given the head of a sorted linked list, delete all nodes that have duplicate numbers (leaving only distinct numbers from the original list) and return the sorted list.

**Example**:

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

## Solution Approach #

The solution involves using two pointers, one to iterate through the list (`current`

) and another to ensure the connection between non-duplicate nodes (`prev`

).

### Algorithm Steps #

- Create a dummy node with next pointing to the head and a
`prev`

pointer pointing to it. - Iterate through the list with the
`current`

pointer. - If duplicates are found, skip them and update the
`next`

of`prev`

. - If no duplicate, move
`prev`

to`current`

. - Continue till the end of the list.
- Return the next of the dummy node, which is the head of the modified list.

### Code (Python) #

```
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def deleteDuplicates(head):
dummy = ListNode(0, head)
prev = dummy
while head:
if head.next and head.val == head.next.val:
while head.next and head.val == head.next.val:
head = head.next
prev.next = head.next
else:
prev = prev.next
head = head.next
return dummy.next
# Test the function
# Example linked list creation and test
head = ListNode(1, ListNode(2, ListNode(3, ListNode(3, ListNode(4, ListNode(4, ListNode(5)))))))
print(deleteDuplicates(head)) # Output: [1, 2, 5]
```

### Time Complexity #

O(n), where n is the number of nodes in the linked list. The list is traversed once.

### Space Complexity #

O(1), as no extra space is used apart from the pointers.