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

题目

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列

思路1

遍历两次，第一次遍历的时候声明一个set集合，存储所有出现过多次的节点，在第二次遍历的时候使用双指针，cur指针在前，pre指针在后，如果发现cur指向的节点在集合中，则将cur向后移动，否则移动pre和cur节点
最终返回事先声明的dom节点，因为head节点指向的值可能多次出现，这里我们不可以直接返回head

复杂度

时间复杂度:

遍历了两次， $O(2n)$

空间复杂度:

存储了出现两次的节点， $O(n)$

Code2

# Definition for singly-linked list.
# 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]:
        s = set()
        if not head: return head
        pre,cur = ListNode(),head
        dom = pre
        while  cur.next:
            if cur.val == cur.next.val:
                s.add(cur.val)
            cur = cur.next

        cur = head
        while cur:
            while cur and cur.val in s:    
                cur = cur.next
            
            pre.next = cur
            
            if not cur: break
            cur = cur.next
            pre = pre.next

        return dom.next

思路2

只声明一个指针cur，在while循环中判断cur.next和cur.next,next是否存在。如果这两个值不等，说明cur.next是不重复出现的，可以当作cur的下一个节点；
否则说明这两个数一样，则这两个数需要去除，我们这里进一个while循环，不断推进cur.next的值，知道cur.next的值得不是最开始出现的那两个相同的数，如果他是none，则此时cur.next就是none，不需要额外操作，如果他是一个数字，且后面还有节点，则继续循环

复杂度2

时间复杂度:

遍历一次： $O(n)$

空间复杂度:

没有声明额外空间： $O(1)$

Code2

# Definition for singly-linked list.
# 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]:
        cur = dumy = ListNode(next=head)
        while cur.next and cur.next.next:
            val = cur.next.val
            if val == cur.next.next.val:
                while cur.next and cur.next.val == val:
                    cur.next = cur.next.next
            else:
                cur = cur.next
        return dumy.next