题解 | #删除链表中重复的结点#
删除链表中重复的结点
https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
//记得：加表头的模式
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead) {
if(pHead==nullptr||pHead->next==nullptr){
return pHead;
}
ListNode * head=(ListNode *)malloc(sizeof(ListNode));
head->next=pHead;
ListNode * nxt=nullptr;
ListNode * lft=pHead;
ListNode * cur =pHead->next;
ListNode * lleft=head;
int rep=0;
while(cur!=nullptr){
if(lft->val!=cur->val){
lft=lft->next;
cur=cur->next;
lleft=lleft->next;
continue;
}
while(cur!=nullptr&&cur->val==lft->val){
//del
nxt=cur->next;
free(cur);
lft->next=nxt;
cur=nxt;
}
free(lft);
lleft->next=cur;
if(cur==nullptr){
break;
}
lft=cur;
cur=cur->next;
}
ListNode * ret=head->next;
free(head);
return ret;
}
};
//1.注意到，要删干净必须要记录left之前的一个节点。因此需要创建头结点
//2.注意处理边缘关系
2.1 只管lft和cur，nxt只在需要删减时计算，减少维护成本
2.2 lleft用于划定左边界
2.3 找到重复序列后，进入删除循环
2.4 删除循环结束后，删除left
2.5 开始重新初始化各个变量
2.5.1 lleft不变、如果没有节点，直接break->表现为cur=nullptr
2.5.2 如果有一个节点，lft=它，cur=nullptr，同样直接break
2.5.3 多个节点，又变成了更小规模的问题。lleft->lft->cur->xxx
先写清楚算法再开始
）