Remove Duplicates

这道题目看似简单,其实很复杂的条件处理感觉。虽然一次AC但是本地debug,逻辑条件改了一次又一次。

首先找重复的prev,然后找到duplicate的后一结点,prev指到后一节点,然后处理多次这种,
因此主体while是 先找前后不等,再找前后相等的,然后吧prev指到p->next,将重复的剪掉。

细节逻辑修改:

  1. while里面只要看p->next就可以了,因为前面保证了p不空,同时记住Knuth的那句过早优化是万恶的源头,最近体会比较深刻,。
    先把逻辑判断写完整来,不处理的也先空着,

2.一开始想着处理head的情况记录first bool值判断第一次 != 循环没做的情况,但是发现这是错误的!因为当前面N次大循环
!=while里都没做的话,都是用head指向后面的p->next, 应该是当prev还没被while体里赋值时,需要head=p->next。

3.漏掉处理前面while循环的另一个条件exit while了。凡是多个条件的while的,一定要处理各个条件退出的情况,例如如果p->next==NULL
了,并且前面连续前后不等,也就是最后尾部连续前后不等,那么可以肯定没啥要remove了,直接退出循环。如果后面==while 因为
p->next退出循环了,那么要注意,可能有最后尾部是多个重复的情况,所以需要加分支判断里面是否做过循环。如果没有的话 break
否则 再看prev是否空,因为还是可能前面一次都没有做过!= while,于是又出来两个分支。

4.最后退出循环是靠两个自循环因为p->next==NULL 退出循环导致的,而不是外层循环。

ListNode *deleteDuplicates(ListNode *head) {
        if(head==NULL || head->next==NULL) return head;

        ListNode*p=head,*prev=NULL;
        int duplicate,noduplicate;
        //bool first=true;
        while(1)
        {
            noduplicate=0;
            while(p->next !=NULL && p->val!=p->next->val)
                prev=p,p=p->next,noduplicate++;
            if(p->next==NULL) break;
            duplicate=0;
            while(p->next !=NULL && p->val==p->next->val)
                p=p->next,duplicate++;
            if(duplicate==0 && p->next==NULL) break;
            else if(p->next==NULL)
            {
                if(prev==NULL)
                    head=NULL;
                else
                    prev->next=NULL;
                break;
            }
            if(duplicate>=1)
            {
                if(prev==NULL)
                {
                    head=p->next;
                    p=head;
                    //first=false;
                }
                else
                {
                    prev->next=p->next;
                    p=prev->next;
                }
            }
            else
            {
                ;
            }
            //first=false;
        }
        return head;
    }

Posted by richard爱闹 - 7月 31 2014
如需转载,请注明: 本文来自 Richard