82. 删除排序链表中的重复元素 II

佚名 6年前 (2019-04-24) 随笔 468人围观抢沙发百度已收录

# 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字,比如：
# 输入: 1->2->3->3->4->4->5
# 输出: 1->2->5
def deleteDuplicates(self, head: ListNode) -> ListNode:
    L = []  #存放所有数字的数组
    while(head!=None):
        L.append(head.val)
        head = head.next
        
    dict0 = {}  #对数组中的每个数字计数，生成字典
    for item in L:
        if L.count(item)<=1:  #个数大于1的数字不加入字典
            dict0.update({item:L.count(item)}) #list.count()方法直接对list中的元素计数！
    L0 = list(dict0.keys())
    L0.sort(key=L.index)   #按照原数组L（即原输入链表）顺序排序
    return L0

#参考评论的代码（用时少）
def deleteDuplicates(self, head: ListNode) -> ListNode:
        dummynode = ListNode(None)
        dummynode.next = head
        pre = dummynode
        while pre.next:
            cur = pre.next
            if cur.next and cur.val == cur.next.val:
                while cur.next and cur.val == cur.next.val:
                    cur = cur.next
                pre.next = cur.next
            else:
                pre = pre.next
        return dummynode.next