题解 | #删除链表中重复的结点#

/*
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

先写清楚算法再开始