Leetcode82-删除排序链表中的重复结点Ⅱ

Leetcode82，难度：Medium

解答：

方法一：记录重复结点的值

ListNode* deleteDuplicates(ListNode* head) {
        ListNode dummy(INT_MIN);
        dummy.next = head;
        ListNode* cur = &dummy;
        int duplicate;//记录当前重复结点的值
        while(cur->next && cur->next->next)//一个结点成不了重复结点
        {
            if(cur->next->val == cur->next->next->val)
            {
                duplicate = cur->next->val;
                while(cur->next && cur->next->val == duplicate)
                {
                    cur->next = cur->next->next;
                }
            }else{
                cur = cur->next;
            }
        }
        return dummy.next;
    }

时间复杂度：n；空间复杂度：1

8ms；64%

方法二：运用“指针的指针”来操作

ListNode* deleteDuplicates(ListNode* head) {
        ListNode **runner = &head;
        if(!head || !head->next) return head;
        while(*runner)
        {
            if((*runner)->next && (*runner)->next->val == (*runner)->val)
            {
                ListNode *temp = *runner;
                while(temp && (*runner)->val == temp->val)
                {
                    temp = temp->next;
                }
                *runner = temp;
            }else
            {
                runner = &((*runner)->next);
            }
        }
        return head;
    }

时间复杂度：n；空间复杂度：1

8ms；64%

方法三：递归解法

ListNode* deleteDuplicates(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* cur = head->next;
        int val = head->val;
        if(cur->val != val)
        {
            head->next = deleteDuplicates(cur);
            return head;
        }else
        {
            while(cur && cur->val == val) cur = cur->next;
            return deleteDuplicates(cur);
        }
    }

方法四：删除排序链表中的重复结点Ⅰ+添加一个bool来处理结点不相等的两种情况

ListNode* deleteDuplicates(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode dummy(head->val);
        dummy.next = head;
        ListNode* pre = &dummy;
        ListNode* cur = head;
        bool isDup = false;
        while(cur && cur->next)
        {
            if(cur->val == cur->next->val)
            {
                isDup = true;
                pre->next = cur->next;
                cur = cur->next;
            }else if(isDup)//不相等有两种情况
            {
                pre->next = cur->next;
                cur = cur->next;
                isDup = false;
            }else
            {
                pre = pre->next;
                cur = cur->next;
            }
        }
        if(isDup){//处理特殊尾结点
            pre->next = nullptr;
        }
        return dummy.next;
    }

时间复杂度：n；空间复杂度：1

✨这里的执行时间和dummy的赋值有特别大的关系（1） 当初始化ListNode dummy(head->val);时候，4ms；100% （2） 当初始化ListNode dummy(head->val+1);时候，8ms （3）当初始化ListNode dummy(INT_MIN);时候，12ms

优化：leetcode同思路完整高效解法——考虑了内存泄露

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
  if (head == NULL) {
        return NULL;
    }
    ListNode *dummyNode = new ListNode(head->val + 1);
    dummyNode->next = head;
    ListNode *cur = head;
    ListNode *pre = dummyNode;
    bool isDeleteCur = false;
    while (cur != NULL) {
        ListNode *next = cur->next;
        if (next == NULL) {
            break;
        }
        ListNode *deleteNode;
        if (cur->val == next->val) {
            isDeleteCur = true;
            deleteNode = next;
            cur->next = next->next;
            delete deleteNode;//防止内存泄露
        } else if (isDeleteCur) {
            deleteNode = cur;
            pre->next = next;
            cur = next;
            isDeleteCur = false;
            delete deleteNode;//防止内存泄露
        } else {
            pre = cur;
            cur = next;
        }
    }
            if (isDeleteCur) {
        pre->next = NULL;
        delete cur;
    }
    ListNode *ret = dummyNode->next;
    delete dummyNode;//防止内存泄露
    return ret;
    }
};

时间复杂度：n；空间复杂度：1

4ms；100%

总结

1.运用“指针的指针”这一类算法非常不熟悉，待强化！！！

2.每道算法题的递归解法都要了解。

3.dummy假结点的初始化是一个值得仔细优化的细节。