public ListNode deleteDuplication(ListNode pHead) {
if (pHead == null || pHead.next == null) {
return pHead;
}
ListNode node1 = pHead;
ListNode node2 = pHead.next;// 比node1快一步
ListNode p = new ListNode(0);
p.next = pHead; // 把头节点也看做普通节点
ListNode node3 = p; // 作为node1的前驱
int v1, v2;
while (node2 != null) {
v1 = node1.val;
v2 = node2.val;
if (v1 == v2) { // 值相等则移动node2,直至不等或null,再更新node1,2,3
node2 = node2.next;
while (node2 != null && node2.val == v1) {
node2 = node2.next;
}
node1 = node2;
node3.next = node2;
if (node2 == null) {
return p.next;
}
node2 = node2.next;
} else {
node3 = node1;
node1 = node1.next;
node2 = node2.next;
}
}
return p.next;
}
时间复杂度o(n),空间复杂度o(1)