203. Remove Linked List Elements

發表於 | 分類於

problem

solution

option 1 - Two Pointers

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

option 2

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *cur = new ListNode(-1), *ret = cur;
        cur->next = head;
        while(cur){
            if(cur->next && cur->next->val == val) cur->next = cur->next->next;
            else cur = cur->next;
        }
        return ret->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *cur = new ListNode(-1), *ret = cur;
        cur->next = head;
        while(cur){
            while(cur->next && cur->next->val ==val) cur->next=cur->next->next;
            cur = cur->next;
        }
        return ret->next;
        
    }
};

analysis

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