跳转至

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

题目

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

示例 1:

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

输出：[1,2,5]

示例 2:

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

输出：[2,3]

思路

虚拟头结点

题解

Go
func deleteDuplicates(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}
    cur := dummy
    for cur.Next != nil && cur.Next.Next != nil {
        val := cur.Next.Val
        if cur.Next.Next.Val == val {
            for cur.Next != nil && cur.Next.Val == val {
                cur.Next = cur.Next.Next
            }
        } else {
            cur = cur.Next
        }
    }
    return dummy.Next
}
Python
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode(next=head)
        while cur.next and cur.next.next:
            val = cur.next.val
            if cur.next.next.val == val:
                while cur.next and cur.next.val == val:
                    cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy.next

复杂度

  • 时间复杂度：\(O(n)\), 其中 \(n\) 为链表的长度。
  • 空间复杂度：\(O(1)\), 仅用到若干额外变量。

参考