题解 | #删除有序链表中重复的元素-II#
删除有序链表中重复的元素-II
http://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024
ListNode* deleteDuplicates(ListNode* head) {
// write code here
if (!head || !head->next) {
return head;
}
ListNode *p1,*pre,*re, *q;
p1 = head;
re = q = NULL;
pre = NULL;
while(p1) {
if ((pre && pre->val == p1->val) || (p1->next && p1->next->val == p1->val)) {
pre= p1;
p1 = p1->next;
continue;
}
if (!re) {
re = q = p1;
} else {
q->next = p1;
q= q->next;
}
pre = p1;
p1 = p1->next;
q->next = NULL;
}
return re;
}
思路：每个节点判断是否是重复的。如果是重复节点就舍弃，否则连接这个节点。
节点是否重复：需要判断当前节点与前一个节点值是否相等，或者后一个节点值是否相等。只要相等就说明错误，否则是不重复的节点。
核心就是这一段：pre 是前驱节点。 p1是当前节点. p1->next 是后驱节点。
while(p1) {
if ((pre && pre->val == p1->val) || (p1->next && p1->next->val == p1->val)) {
// 与前驱结点值相等 或者 与后一个节点值相等，说明是重复节点，直接丢弃
pre= p1;
p1 = p1->next;
continue;
}
// 到这里说明是非错误节点，直接放到结果链表中
if (!re) {
re = q = p1;
} else {
q->next = p1;
q= q->next;
}
pre = p1;
p1 = p1->next;
// 注意插入节点后要更新最后节点指向 NULL。
q->next = NULL;
}
