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

题目#

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

示例 1:

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

示例 2:

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

思路#

记录节点是否重复出现最简单的方法可能就是开个 map 了，当然我们也确实可以这样做。

但题目中还有一个条件是 排序链表，因此我们可以避免额外空间的开辟。

代码#

func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return head
    }

    dummy := &ListNode{0, head}
    head = dummy

    // 防止空指针错误
    for head.Next != nil && head.Next.Next != nil {
        // 重复
        if head.Next.Val == head.Next.Next.Val {
            rmVal := head.Next.Val

            // 对所有重复的节点依次断链
            for head.Next != nil && head.Next.Val == rmVal {
                head.Next = head.Next.Next
            }
        } else {
            head = head.Next
        }
    }

    return dummy.Next
}