82_删除排序链表中的重复元素_II

类型：链表

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

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

  ❓ 给定一个升序排列的链表，请删除链表中「所有」数值重复的节点。不破坏剩下结点的升序排列。

  💡 一次遍历

  我们进行一次遍历，即可完成删除操作。由于头结点也可能删除，因此我们可以增加一个虚拟结点指向头结点。

  class Solution:
      def deleteDuplicates(self, head: ListNode) -> ListNode:
          if not head:
              return head
  
          dummy = ListNode(0, head)
  
          cur = dummy
          while cur.next and cur.next.next:
              if cur.next.val == cur.next.next.val:
                  x = cur.next.val
                  while cur.next and cur.next.val == x:
                      cur.next = cur.next.next
              else:
                  cur = cur.next
  
          return dummy.next

  时间复杂度：O(n)，空间复杂度：O(1)