方法:双指针(如果算的话)
因为要把所有重复元素全部删除,所以使用遍历指针遍历过程中,发现第一个重复元素的位置,其前驱要保存下来,于是就用两个指针遍历(
和
),当然,为了处理头结点的特殊情况,设置虚拟头结点更方便。代码如下:
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)