83. Remove Duplicates from Sorted List

發表於 | 分類於

problem

solution

option 1 - Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return head;
        ListNode *slow = head, * fast = head;
        while(fast){
            if(slow->val !=fast->val){
                slow->next = fast;
                slow = slow=slow->next;
            }
            fast = fast->next;
        }
        slow->next = nullptr;
        return head;
    }
};
  • other version
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            if(!head) return head;
            ListNode *ret = new ListNode(-1), *ans = ret;
            ret->next = new ListNode(head->val);
            ret = ret->next;
            head= head->next;
            while(head){
                if(head->val!=ret->val){
                    ret->next = head;
                    ret =ret->next;
                }
                head= head->next;
            }
            ret->next = nullptr;
            return ans->next;
        }
    };

option 2 - improve option 1

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return nullptr;
        ListNode *p = head;
        while(p){
            while(p->next && p->val ==p->next->val) p->next = p->next->next;
            p=p->next;   
        }
        return head;
    }
};

option 3 - use STL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return nullptr;
        set<int> s;
        ListNode *ret = new ListNode(-1), *ans = ret;
        // 利用set ordered
        for(ListNode *p = head;p;p=p->next) s.insert(p->val);
        
        for(auto iter = s.begin(); iter!=s.end();iter++){
            ret->next = new ListNode(*iter);
            ret= ret->next;
        }
        return ans->next;
    }
};

analysis

  • time complexity O(n)
  • space complexity O(1)