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

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

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5

示例 2:

输入: 1->1->1->2->3
输出: 2->3

通过次数52,638 | 提交次数109,156

First Try

2020-07-06

使用dummy节点放在head前面，真是简化了很多起点的边界考虑。这种要删除遍历的节点在内的操作，只能够提前保留该节点前面安全的节点了，这样才能不被断开。因为还可能删除当前节点的前一个节点，因此需要提前保留两个节点。在删除后如果再遇上，则需要通过visited缓存来进行删除的判断。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 没看出有什么考点？
        # 链标本身也不需要排序啊？还是说其实不允许出现额外空间set的使用？
        # 第一次测试才知道是只要有重复的就把所有都删除
        if not head:
            return head 
        dummy = ListNode(None)
        dummy.next = head 
        prepre = dummy 
        pre = head 
        visited = set()
        while pre.next:
            node = pre.next     
            if node.val == pre.val or node.val in visited:
                prepre.next = node.next 
                pre = prepre
            else:
                prepre = pre 
                pre = node 
            visited.add(node.val)  
        return dummy.next 

执行用时：20 ms, 在所有 Python 提交中击败了99.35%的用户
内存消耗：12.7 MB, 在所有 Python 提交中击败了9.52%的用户

82. 删除排序链表中的重复元素 II [medium]​

First Try​

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

First Try