美文网首页
82. Remove Duplicates from Sorte

82. Remove Duplicates from Sorte

作者: 蜜糖_7474 | 来源:发表于2019-06-07 17:10 被阅读0次

    Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

    Example 1:

    Input: 1->2->3->3->4->4->5
    Output: 1->2->5

    Example 2:

    Input: 1->1->1->2->3
    Output: 2->3

    AC代码

    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            if (!head || !(head->next)) return head;
            ListNode *nope = new ListNode(-1), *ret = nope;
            nope->next = head;
            ListNode* pre = head;
            head = head->next;
            while (head) {
                if (pre->val != head->val) {
                    head = head->next;
                    pre = pre->next;
                    nope = nope->next;
                }
                else {
                    while (head->next && head->next->val == head->val) {
                        head = head->next;
                        pre = pre->next;
                    }
                    nope->next = head->next;
                    if (head->next && head->next->next) {
                        pre = head->next;
                        head = head->next->next;
                    }
                    else break;
                }
            }
            return ret->next;
        }
    };
    

    优化代码

    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            ListNode *pre = new ListNode(-1), *ret = pre;
            pre->next = head;
            while (pre->next) {
                head = pre->next;
                while (head->next && head->next->val == head->val)
                    head = head->next;
                if (head == pre->next)
                    pre = pre->next;
                else
                    pre->next = head->next;
            }
            return ret->next;
        }
    };
    

    递归代码

    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            if (!head || !(head->next)) return head;
            ListNode* p = head->next;
            if (p->val != head->val) {
                head->next = deleteDuplicates(p);
                return head;
            }
            else {
                while (p && p->val == head->val) p = p->next;
                return deleteDuplicates(p);
            }
        }
    };
    

    总结

    一开始自己写的循规蹈矩,同时移动三个指针,效率上很低,很憨憨,稍微改进了一下好很多。递归代码参考:https://www.cnblogs.com/AndyJee/p/4467051.html

    相关文章

      网友评论

          本文标题:82. Remove Duplicates from Sorte

          本文链接:https://www.haomeiwen.com/subject/bcwmxctx.html