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

思路

从字面意思来看可以直接写出代码

function deleteDuplicates(head: ListNode | null): ListNode | null {
    let p1 = head

    while (p1) {
        if (p1.val === p1.next?.val) {
            p1.next = p1.next.next
        }
        p1 = p1.next
    }

    return head
}

但是如上代码，如果是三个相等的数字就会出现如下结果

input: [1,1,1]
output: [1,1]
expect: [1]

input: [0,0,0,0,0]
output: [0,0,0]
expect: [0]

可以进行调试, 在第一次循环的时候 p1.next = p1.next.next 得到了 [1,1], 然后执行下一行代码 p1 = p1.next, 也就是 1 = null, null 被赋值给了值是 1 的 p1

然后进行下一轮循环 while(null) 退出循环， 得到结果 [1,1]

第二个 [0,0,0,0,0] 的案例也是同样道理，只会执行一半的去重操作

经过上述描述，p1 = p1.next 这一行代码在跟下一个节点数据一样的时候不应该被执行到，不然就会出现上面的代码, 也就是把这一行代码放到 else 去执行即可

如下代码所示:

function deleteDuplicates(head: ListNode | null): ListNode | null {
    let p1 = head

    while (p1) {
        if (p1.val === p1.next?.val) {
            p1.next = p1.next.next
        } else {
            p1 = p1.next
        }
    }

    return head
}

复杂度分析

时间复杂度： O(N) ，因为就一个 while 循环体

空间复杂度： O(1)， 因为没有额外的变量存储, 就一个 let p = head , 没有任何的线性增长数据