82. Remove Duplicates from Sorted List II.md

82. Remove Duplicates from Sorted List II

https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

Given 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: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

Input: 1->1->1->2->3
Output: 2->3

代码

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        dummy = ListNode(0, head)
        # predecessor always points to the last non-duplicate element 
		pred = dummy	

        while head:
            if head.next and head.val == head.next.val:
                while head.next and head.val == head.next.val:	# keep skipping
                    head = head.next
                
                pred.next = head.next	# here, head.next is no longer the duplicate
            
            else:
                pred = pred.next
            
            head = head.next	# move to next element
        
        return dummy.next