链表问题_删除排序链表中的重复节点

迈不过友情╰ 2022-05-21 07:46 218阅读 0赞

题目：在一个排序链表中删除其中重复的节点，重复的一个不留。  
分析：若我们定义的函数无返回值则应该讲函数的参数定义成\*\*phead，因为头结点也可能被删除，具体的实现如下：

struct ListNode {
           int val;
            struct ListNode *next;
            ListNode(int x) :
                  val(x), next(NULL) {
            }
      };
    void deleteDuplication(ListNode**phead)
    {
        if(phead==NULL || *phead==NULL)
            return;
        ListNode*pPreNode =NULL;//作为待删除节点的前驱
        ListNode *pNode=*phead;
        while(!pNode)
        {
            ListNode*pNext=pNode->next;//指向删除节点之后的一个节点
            bool needdelete=false;
            if(pNext!=NULL && pNext->val==pNode->val)
                needdelete=true;
            if(!needdelete)
            {
                pPreNode=pNode;
                pNode=pNode->next;
            }
            else
            {
                ListNode* p_delete=pNode;
                int value=pNode->val;
                while(p_delete!=NULL && p_delete->val==value)
                {
                    pNext=p_delete->next;
                    delete p_delete;
                    p_delete=NULL;
                    p_delete=pNext;
                }
                if(pPreNode==NULL)  //删除的是头结点
                    *phead=pNext;
                else
                    pPreNode->next=pNext;
                pNode=pNext;
            }
        }
    }

若我们定义的函数可以返回ListNode\*，那么该函数的参数可以是ListNode\*。具体的可以实现为递归版本和迭代版本，迭代版本方法和上述一样，这里不再赘述。给出对应的递归版本实现如下：

ListNode* deleteDuplication(ListNode*phead)
    {
        if(phead==NULL)
            return phead;
        if(phead->next==NULL)
            return phead;
    
        if(phead->val==phead->next->val)
        {
            ListNode*pnode=phead;
            int value=phead->val;
            while(pnode!=NULL&&pnode->val==value)
            {
                ListNode*pnext=pnode->next;
                delete pnode;
                pnode=NULL;
                pnode=pnext;
            }
            return deleteDuplication(pnode);
        }
        else
        {
            phead->next= deleteDuplication(phead->next);
            return phead;
        }
    }