删除链表中重复的结点

时间:2021-06-18 22:15:08

题目描述

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5

思路

  1. 如果链表为空,或者只有一个结点,直接返回
  2. 如果链表结点大于等于2,则比较当前结点和下一个结点是否相同,如果相同,则删除当前结点和下一个结点,比较下下个结点是否和当前结点相同,如果相同继续删除,直至与当前结点不同。
  3. 返回链表表头是第一个不重复结点,需要一个前驱结点prenode记录不重复链表,其next应该初始为NULL,如果有下一个不重复结点,则next是下一个不重复结点。
  4. 测试用例:
    a. 空
    b. 一个结点
    c. 两个重复结点
    d. 1->1->2->3
    e. 1->2->3->3->4->4
    具体见code

code

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {

        ListNode* phead=NULL;
        if(pHead==nullptr)
            return phead;
        ListNode* pnode=pHead;
        ListNode *prenode=NULL;
        bool tobedelete=false;
        while(pnode)
        {
            ListNode* pnext=pnode->next;
            tobedelete=false;
            if(pnext&&pnext->val==pnode->val)
            {
                tobedelete=true;
            }else{
                if(phead==NULL)
                {
                    phead=pnode;
                    prenode=phead;
                }
                else {
                    prenode->next=pnode;
                    prenode=pnode;
                    prenode->next=NULL;
                }
                pnode=pnext;
            }
            if(tobedelete)
            {
                int val=pnode->val;
                ListNode* pdelete=NULL;
                while(pnode&&pnode->val==val)
                {
                    pdelete=pnode;
                    pnode=pdelete->next;
                    delete pdelete;
                    pdelete=NULL;
                }
            }
        }
        return phead;
    }
};

code注意事项

  1. 注意链表结点删除,需要赋值为NULL
  2. 不重复链表最后一个结点next初始值应该是NULL,即1->2->2->4->5->5这种情况下,如果非NULL,则会最后两个野指针,出错。