题解 | #删除有序链表中重复的元素-II#

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
#桶排序，仅python可用桶排序，由于list下标可以为负数缘故
#数值范围为绝对值
class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        if not head:
            return None
        bucket = [0 for i in range(2001)] #|val|<1000, 大于1000的存放负数
        while head:
            bucket[head.val] += 1 #head.val为负数时，由python列表性质，存放数据的下标位置为1000~2000之间
            head = head.next
        res = ListNode(-1) #正数链
        cur = res
        mres = ListNode(-1) #负数链
        mcur = mres
        for i in range(len(bucket)):
            if i <= 1000 and bucket[i] == 1:
                newNode = ListNode(i)
                cur.next = newNode
                cur = newNode
            if i > 1000 and bucket[i] == 1:
                newNode = ListNode(i-2001)
                mcur.next = newNode
                mcur = newNode
            mcur.next = res.next
        return mres.next