64.删除排序链表中的重复元素 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
- 题目数据保证链表已经按升序 排列
思路
注意题目要求是删除所有的重复数字，不是每一个都保留一份
因为链表已经排序，所以所有相同的数字必然是挨在一起的(连续的一片)。
这样我们只要发现某个值和它后面的值相同，就直到这是一片重复区，把这一整片连续的相同节点全部删除掉即可。
如果没有排序，相同的数字散落各处，就没法用这种扫一遍的简单办法。
我们需要一个指针prev,让它始终停在已确认不重复的那部分的最后一个节点上，然后用它去探查后面:
- 看prev.next和prev.next.next这两个节点的值是否相同
- 如果相同说明从prev.next开始是一片重复区，我们把这一整片值相同的节点全部跳过，然后 让prev.next直接接到重复区后面的第一个不同节点。
注意这一步prev自己不动，因为它后面新接上的节点还没验证过是否也重复。
- 如果不同说明prev.next是个干净的、独一无二的节点，可以保留，这时prev往前移动一步(prev = prev.next)
dummy哨兵节点
为什么需要它？ 因为头结点自己就可能是重复的(比如[1,1,1,2,3]，开头的1就要被删光)。
这时已确认不重复部分的最后一个节点根本不存在。
加一个dummy指向head，让prev从dummy出发，这样即使要删掉包括头结点在内的一整片，dummy也稳稳的在前面兜底，不用判断，最后返回dummy.next。
class ListNode(var `val`: Int) {
var next: ListNode? = null
}
class Solution {
fun deleteDuplicates(head: ListNode?): ListNode? {
// 1. 哨兵节点，指向 head，统一处理"头节点也是重复的"边界情况
val dummy = ListNode(0)
dummy.next = head
// 2. prev 始终停在"已确认不重复部分的最后一个节点"，从 dummy 出发
var prev: ListNode = dummy
// 3. 只要 prev 后面还有至少两个节点，就能比较是否重复
while (prev.next != null && prev.next!!.next != null) {
if (prev.next!!.`val` == prev.next!!.next!!.`val`) {
// 发现重复区：记下这个重复的值
val duplicateVal = prev.next!!.`val`
// 把所有值等于 duplicateVal 的节点全部跳过
while (prev.next != null && prev.next!!.`val` == duplicateVal) {
prev.next = prev.next!!.next
}
// 注意：prev 不动，因为新接上的节点还没验证过
} else {
// 不重复：prev.next 是干净节点，prev 前进一步
prev = prev.next!!
}
}
// 4. 返回真正的头节点
return dummy.next
}
}
代码里两个 while 的分工
这道题是双层循环，两个 while 各司其职，别搞混：
- 外层 while：控制 prev 从头扫到尾，逐个位置检查。
- 内层 while：一旦发现重复区，负责把这一整片相同值的节点连续删干净。
复杂度
- 时间复杂度: O(n)：虽然是双层循环，但每个节点最多被访问常数次（要么被 prev 走过一次，要么在内层被删除时经过一次），总量和链表长度成正比。
- 空间复杂度: O(1)：只用了 dummy、prev 几个指针，没有额外空间。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!