题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留。

样例

输入：1->2->3->3->4->4->5

输出：1->2->5

输入：1->1->1->2->3

输出：2->3

算法1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        //判断头结点是否为空
        if(!head) return NULL;

        auto t = head;
        //cout<<"t address = "<<t<<" and head address is "<<head<<endl;
        /*   取一个bool值记录当前节点是否为重复元素，
         *   用于删除重复元素的最后一个元素（即前面的重复元素均被删除后遗
         *   留的最后一个元素，比如4,4,4,前2个4删除后，剩下的最后一个4）
         */
        bool flag = false;
        while(t)
        {
            //cout<<"current t->val  = "<<t->val<< "and the flag is "<<flag <<endl;
            //若此节点为最后一个节点，跳出循环
            if(!t->next){
                //cout<<"t->next is null"<<endl;
                break;
            };
            //cout<<"before1 "<<t->val<<endl;
            //若前后两个节点重复，删除本节点，置重复元素标志位为true
            if(t->val == t->next->val)
            {
                //cout<<"before "<<t->val<<endl;
                flag = true;
                auto c = t->next;
                t->val = c->val;
                t->next = c->next;

                //cout<<"after "<<t->val<<endl;
                delete c;
            }
            //若为重复节点的最后一个节点，删除
            else if(flag)
            {

                auto c = t->next;
                t->val = c->val;
                t->next = c->next;
                flag = false;
                delete c;
            }
            //若不是上述两种情况，移动到下一节点
            else
            {
                t = t->next;
                //cout<<"after1 "<<t->val<<endl;
                //cout<<endl;
            }

        }

        //若链表只剩下最后一个节点并且为重复节点，返回NULL
        if(flag && !head->next) head = NULL;
        //否则删除本节点
        else if(flag)
        {
            auto a = head;
            while(a->next != t)
            {
                a = a->next;
            }
            a->next = NULL;
            delete t;
        }

        //else t = NULL;
        //cout<<"t address = "<<t<<" and head address is "<<head<<endl;
        return head;
    }
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla