Problem description:

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:

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

Example 2:

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

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 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: ListNode) -> ListNode:
        if not head:
            return head
        dummy = ListNode(-1)
        dummy.next = head
        fast, slow = head, dummy
        while fast and fast.next:
            if fast.val == fast.next.val:
                while fast and fast.next and slow.next.val == fast.next.val:
                    fast = fast.next
            
                slow.next = fast.next
                
            else:
                slow = slow.next
            fast = fast.next
        return dummy.next

time complexity: $O(n)$
space complexity: $O(1)$
reference:
related problem: