- 新增一个头结点h用于结果链表。对于链表每一个不为空的结点p1,我们有两种处理:
- 如果存在后继结点并且后继结点的值等于这个节点的话:
1 递增p1直至它的后继结点值不等于他
2 再次递增p1,若p1为空则返回当前结果。否则p1此时指向的就是前几个重复结点之后的第一个新结点。 - 否则:令结果链表指向该节点,该节点递增。
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead) {
if(!pHead)
return NULL;
if(!pHead->next)
return pHead;
ListNode *h = new ListNode(0);
ListNode *p = h;
ListNode *p1 = pHead;
while(p1) {
if(p1->next && p1->next->val == p1->val) {
while(p1->next && p1->next->val == p1->val) {
p1 = p1->next;
}
p1 = p1->next;
if(!p1)
return h->next;
}else {
ListNode *q = p1;
p1 = p1->next;
p->next = q;
p = p->next;
p->next = NULL;
}
}
return h->next;
}
};