题目描述

blablabla

样例

blablabla

算法1

(线性扫描) $O(n)$

blablabla

时间复杂度

参考文献

C++ 代码

/**
 * 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) {
        auto v_head = new ListNode(-1);
        v_head -> next = head;

        auto p = v_head;
        while(p -> next){
            auto t = p -> next;
            while(t && p -> next -> val == t -> val)    t = t -> next;  // t至少向后走1位：因为初始t的值一定等于p -> next的值；当t不为空且值一直等于p的next(固定)时，往后走
            if(p -> next -> next == t)  p = p -> next;  // 如果中间只走了1位，则p直接等于下一位
            else    p -> next = t;  // 否则p的下一位等于现在的t（相当于把p + 1到t - 1中间的删除）
        }
        return v_head -> next;
    }
};

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla