203. Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example:

Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

// Iteration
ListNode* removeElements(ListNode* head, int val) { // time: O(n); space: O(1)
    ListNode* dummy = new ListNode(-1), *pre = dummy;
    dummy->next = head;
    while (pre->next) {
        if (pre->next->val == val) {
            ListNode* t = pre->next;
            pre->next = t->next;
            delete t;
        } else {
            pre = pre->next;
        }
    }
    ListNode* res = dummy->next;
    delete dummy;
    return res;
}

// Recursion
ListNode* removeElements(ListNode* head, int val) { // time: O(n); space: O(n)
    if (!head) return nullptr;
    head->next = removeElements(head->next, val);
    return head->val == val ? head->next : head;
}