题解 | #删除有序链表中重复的元素-II#

题解一：迭代
题解思路： 利用一个变量记录重复元素个数，修改链表相应节点的next
图示：

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(1)
实现如下：

class Solution {
public:
    /**
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        if(!head||!head->next) return head; //空或者一个节点
        ListNode* kong = new ListNode(0); //空白节点
        kong->next = head;  //指向头
        //初始化p,q,t
        ListNode* p = kong; 
        ListNode* q = head;
        ListNode* t = head->next;
        //当前有无重复
        int num = 0;
        while(t){
            if(q->val == t->val) {t = t->next; num = 1;} // q->val ==t ->val ：移动t 且将num 设置为1
            else {
                if(num!=0){  //如果不同，且num不为0
                  p->next = t;  //p指向t
                  num = 0;  //重置零
                }
                else {
                   p = q; 
                }
                //移动q,t
                q = t;
                t = t->next;
            }
        }
        //这一步判断倒数第二个与倒数第一个是不是重复
        if(num) p->next = t;
        return kong->next;

    }
};

题解二：递归
递归分析：
递归边界： head为空或者head->next 为空
递归调用： head->val ! = head->next->val,说明当前节点与其下一个节点不等，保留当前节点。 对其下一个节点递归
head->val == head->next->val, 说明当前节点与其下一个节点相等，那么就一直删除到与head->val不等为止
图示：

复杂度分析：
时间复杂度：O(N)
空间复杂度：O(N)
实现如下：

class Solution {
public:
    /**
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head||!head->next) return head; //递归边界
        if(head->val != head->next->val) head->next = deleteDuplicates(head->next);
        else {
            ListNode* p = head->next;
            while(p && head->val ==p->val) p = p->next;
            return deleteDuplicates(p);
        }
        return head;
    }
};