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

//如果是未排序的链表，用桶来记录。但这题是已排序的，所以空间复杂度只要O1就够了。我们记录当前的节点，判断它与下一个节点是否相同即可。
//整体思路是简单的，但是一些细节处理比较麻烦。比如这题要求把所有重复的节点都删掉，比如1233445要求删除成125而不是12345，这要求我们把Previous也删掉，所以需要一个Entry来记录重复的入口节点。以便删除完一整串重复的数字后能将入口的next指向“对岸”
//再比如，有可能链表的开头就发生重复了，这样的话我们返回的链表的位置也必须从pHead往后挪。有可能还不止得挪一次。
//还比如，把整个链表删干净了的情况。
//落到实处时，还要考虑删完一段重复的节点后，接下来离链表结束只剩1个或0个节点的情况。
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if(pHead==nullptr || pHead->next==nullptr)//确保至少有两个节点
            return pHead;
        int Val=pHead->val;
        bool bDeletedHead=false;//是否删除掉了入口节点。
        bool bDeletedTail=false;//是否删除掉了尾巴
        ListNode* result=pHead;
        ListNode* currentNode=pHead->next;
        ListNode* PreviousNode=pHead;
        ListNode* Entry=new ListNode(-1);//重复的入口节点
        Entry->next=PreviousNode;
        int repeatedVal=0;//因为要把所有重复的值都删掉，而不是只删一个。
        int ListLength=0;//记录链表的长度，如果最后删干净了就返回空。
        while (currentNode) {
            if(currentNode->val==Val)//如果发生了重复，说明这时的Previous与currentNode都是重复的，都得删。但一个个来。
            {
                repeatedVal=currentNode->val;
                //说明在入口处就重复了，需要注意的是，入口可能会被多次删除。比如11122335678，这样的话，返回的result的位置要连续变3次。
                if(PreviousNode==result)
                    bDeletedHead=true;
                while (currentNode) {
                    if(currentNode->val==repeatedVal)
                    {
                        PreviousNode->next=currentNode->next;
                        delete currentNode;
                        currentNode=PreviousNode->next;
                        if(currentNode==nullptr)//说明链表末尾已被删
                            bDeletedTail=true;
                    }else {
                        break;
                    }
                }
                delete PreviousNode;
                PreviousNode=currentNode;
                if(bDeletedHead==true)
                {
                    result=PreviousNode;
                    bDeletedHead=false;//挪动一次result的位置，下次可能还得再挪，所以把其置为false。
                }
                if(bDeletedTail)//如果尾巴都删了那早该结束了
                {
                    Entry->next=nullptr;
                    return result;
                }
                Entry->next=PreviousNode;
                Val=PreviousNode->val;
                if(currentNode->next==nullptr)
                {
                    ListLength++;//如果删光这段重复的数字后，链表的后面还能剩2个节点，那就让currentNode再挪一格，一切正常进行。否则，代表后面只有一个节点了，currentNode没地方挪，剩下一个数字也不可能发生重复，我们让ListLength+1就结束。
                }
                currentNode=currentNode->next;
                continue;
            }else {
                Entry=PreviousNode;
                PreviousNode=currentNode;
                Val=PreviousNode->val;
                currentNode=currentNode->next;//如果没发生重复，都往前步进一格
                ListLength++;
            }
        }
        if(ListLength<=0)
            return nullptr;
        return result;
    }
};