删除链表中重复的节点
删除链表中重复的节点
题目描述
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
ListNode* deleteDuplication(ListNode* pHead)
{
if(pHead==NULL)
return pHead;
//创建一个虚拟头节点,其next指向pHead,并使p,q指向该虚拟头节点
ListNode* q=new ListNode(0);//创建一个虚拟头节点
ListNode* p=q;
p->next=pHead;
while(p->next!=NULL){ //先不要管这层while,弄清楚里面的自然就直到了这里该怎么写了
//考虑p后面的两个节点,因为如果重复至少两个,否则就到尾了
//当存在两个实节点并且这两个节点不相等,p就前进一个节点,这样保证p始终不与它下一个节点相等
//因此,终止时要么p->next->next==NULL,否则,p指向第一个重复元素的前一个节点。
while(p->next->next!=NULL && p->next->val!=p->next->next->val){
p=p->next;
}
如果出现重复则找到最后一个重复的元素并使p->next=c->next
if(p->next->next!=NULL && p->next->val==p->next->next->val){
ListNode* c=p->next;
while(c->next!=NULL && c->val==c->next->val){
c=c->next;
}
p->next=c->next;
}
else if(p->next->next==NULL)
break;//到结尾了直接break
//这样一次循环下来,就删除掉了第一个重复元素,此时p->next指向原重复元素的下一个节点,然后只要p->next!=NULL,就再来一遍(就像一开始时p->next==pHead,pHead不为空)
}
return q->next;//然后返回头节点
}`
清爽版完整题解
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
if(pHead==NULL)
return pHead;
ListNode* q=new ListNode(0);
ListNode* p=q;
p->next=pHead;
while(p->next!=NULL){
while(p->next->next!=NULL && p->next->val!=p->next->next->val){
p=p->next;//p指向重复元素的前一个节点
}
if(p->next->next!=NULL && p->next->val==p->next->next->val){
ListNode* c=p->next;
while(c->next!=NULL && c->val==c->next->val){
c=c->next;
}
p->next=c->next;
}
else if(p->next->next==NULL)
break;
}
return q->next;
}
};