LeetCode 82. Remove Duplicates from Sorted List II - Linked List series question 11

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: Output: [1,2,5]

Example 2: 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.

# 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]:

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

# 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]:
return None

while cur and cur.val == head.val:
cur = cur.next