题解 | #删除有序链表中重复的元素-II#
https://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024
方法：双指针（如果算的话）
因为要把所有重复元素全部删除，所以使用遍历指针遍历过程中，发现第一个重复元素的位置，其前驱要保存下来，于是就用两个指针遍历（和
），当然，为了处理头结点的特殊情况，设置虚拟头结点更方便。代码如下：
public ListNode deleteDuplicates (ListNode head) {
ListNode pre = new ListNode(-1); // 新建虚拟头结点，pre在遍历过程中保存p的前驱结点
pre.next = head;
ListNode p = head, pHead = pre; // p为遍历指针，pHead始终保存头结点的前驱
while (p != null && p.next != null) {
if (p.val != p.next.val) { // p和p.next不等时两指针同时移动
pre = pre.next;
p = p.next;
} else {
// p和p.next相等时，（p.next不为空时）一直往后找知道第一个不相等的位置
while (p.next != null && p.val == p.next.val) {
p = p.next;
}
pre.next = p.next; // 删除pre到p的重复元素
p = p.next; // 内圈while结束时，p停在这波相同元素的最后一个上，删除后需重置p的位置为下一个
}
}
return pHead.next;
}
时间复杂度：O(N)，空间复杂度：O(1)
查看15道真题和解析