题解 | #删除有序链表中重复的元素-II#

摸了两天的🐟qaq，终于回来了，不过脑子有点生了>w<

言归正传，这道题相比于上一道题增加的功能是要求将重复的元素全部删除，而且要求的空间复杂度为O(1)，这就意味着我们需要在原本的链表上操作了。

因为考虑到头节点就有可能是重复的节点，所以我们准备在原本的head的前面添加一个pre_head作为新的头节点，这个节点在后续程序中会认为是已完成重复性判断的节点~

因为我们需要在原本的链表上进行删除操作，因此还需要一个aft_head在原本的head的后面，当然aft_head还需要担任重复性判断的任务

最后我们需要一个detect_repeat用于重复性判断~

讲完了我们会用到的新变量，我们该来准备算法流程啦~

主要的流程是，判断head当前的节点是否为重复的节点，如果是重复的，则需要一直进行判断+删除操作，直到删除完所有的重复节点，如果不是重复节点则进行常规的->next操作

现在我们来说一下边界状态，简单的单个节点链表以及空链表就不说了

首先是头节点就是重复元素的情况，由于pre_head的使用头节点重复不会导致影响

然后就是尾节点是重复元素，这就意味着aft_head会是NULL的情况

        if(detect_repeat==aft_head->val)//有重复的，需要删除重复的第一个元素
        {
            while(head->val==detect_repeat)
            {
                pre_head->next = aft_head;
                if(head==output)
                {
                    output = output->next;
                }
                free(head);
                head = pre_head->next;
                if(head==NULL)
                {
                    break;
                }
                if(aft_head!=NULL)
                {
                    aft_head = aft_head->next;
                }
            }
        }

所以我们需要添加aft_head!=NULL的条件以及在head==NULL的情况下break的条件

最后添加一下完整的函数代码，这道题我也通过的莫名其妙的QAQ，大佬们看到问题请劳烦评论区告知我感谢感谢~

struct ListNode* deleteDuplicates(struct ListNode* head ) {
    struct ListNode* pre_head = (struct ListNode*)malloc(sizeof(struct ListNode));
    if(pre_head!=NULL)
    {
        pre_head->next = head;
        pre_head->val = -1001;
    }
    if(pre_head->next==NULL)
    {
        return NULL;
    }
    int detect_repeat = -1001;
    struct ListNode* aft_head = (struct ListNode*)malloc(sizeof(struct ListNode));
    if(aft_head!=NULL)
    {
        aft_head = head->next;
    }
    if(aft_head==NULL)
    {
        return head;
    }
    struct ListNode* output = head;
    while(aft_head!=NULL)
    {
        detect_repeat = head->val;
        if(detect_repeat==aft_head->val)//有重复的，需要删除重复的第一个元素
        {
            while(head->val==detect_repeat)
            {
                pre_head->next = aft_head;
                if(head==output)
                {
                    output = output->next;
                }
                free(head);
                head = pre_head->next;
                if(head==NULL)
                {
                    break;
                }
                if(aft_head!=NULL)
                {
                    aft_head = aft_head->next;
                }
            }
        }
        else 
        {
            pre_head = pre_head->next;
            head = head->next;
            aft_head = aft_head->next;
        }
    }
    return output;
}