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:

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

Example 2:

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.

This question is similar to LeetCode 83. Remove Duplicates from Sorted List The difference is that this problem requires that all nodes with the same value be deleted. Similarly, for an ordered linked list, nodes with the same value must be continuous in the linked list. Therefore, for a node, you can find all nodes with the same value at one time and delete them. There are also iterative and recursive solutions to this problem.

Iterative method: define two pointers cur and pre to point to the current node and its parent node respectively, and traverse the whole linked list. For the current node, judge whether there is a node with the same value after the current node. Since the equal nodes must exist continuously, a pointer end can be used to point to the last node with the same value as the current node. If end and cur point to different nodes, it indicates that there is a node with the same value as the current node, You need to delete them all (pre.next points to end.next), the pointer pre remains unchanged, and the pointer cur is updated to point to end Next, enter the next cycle; If there is no node equal to the current node value, the pointer pre points to cur and cur points to cur Next, enter the next cycle.

# 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]:
        preHead = ListNode(0, head)
        
        pre, cur = preHead, head
        
        while cur:
            end = cur
            while end.next and end.next.val == cur.val:
                end = end.next
            if end != cur:
                pre.next = end.next
                cur = end.next
            else:
                pre = cur
                cur = cur.next
        
        return preHead.next

Recursive method: for the input linked list of recursive calls, if the number of nodes is less than or equal to 1, the header node pointer is returned directly without any processing; If the number of nodes is greater than or equal to 2, you need to judge that there is a node equal to its value after the head node. Define a pointer cur to the header node head, and then start searching to make cur point to the first header node head Nodes with unequal Val values, and then recursively call to process the linked list starting from cur (the first node with unequal head values) and return a new header newHead. If the pointer cur does not point to head Next, it indicates that there are multiple nodes with the same value. You need to delete them all and directly return to the new header node newHead; If the pointer cur points to head Next, indicating that there are no multiple nodes with the same value. The old head node needs to be retained and the head Next points to the new header node newHead and returns head.

# 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]:
        if not head:
            return None
        
        cur = head
        while cur and cur.val == head.val:
            cur = cur.next
        
        newHead = self.deleteDuplicates(cur)
        if cur == head.next:
            head.next = newHead
        else:
            head = newHead
        
        return head