203. Remove Linked List Elements.md

203. Remove Linked List Elements

1. Description

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Example 1:

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:

Input: head = [], val = 1
Output: []

Example 3:

Input: head = [7,7,7,7], val = 7
Output: []

Constraints:

• The number of nodes in the list is in the range [0, 10^4].
• 1 <= Node.val <= 50
• 0 <= val <= 50

2. Solutions

Solution 1: Language: C Two Loops

See comments in codes.

• Tuesday, 01 March, 2022
• Time Complexity: $O(n)$
• Space Complexity: $O(1)$
• Runtime: 12 ms, faster than 87.59% of C online submissions for Remove Linked List Elements.
• Memory Usage: 8.3 MB, less than 8.86% of C online submissions for Remove Linked List Elements.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

// NOTE: The "free()" function is used to defend memory leaking.
struct ListNode *removeElements(struct ListNode *head, int val) {
    // Remove required elements at the head of the list.
    while (head != NULL && head->val == val) {
        struct ListNode *destory = head;
        head = head->next;
        free(destory);
        destory = NULL;
    }

    // Because we skip all removed starting elements, the new head
    // must be a "NULL" or a node that "head->val != val".
    if (head == NULL) {
        return NULL;
    }

    // Therefore, we could compare elements from the second node.
    struct ListNode *curr = head;
    while (curr->next != NULL) {
        if (curr->next->val == val) {
            struct ListNode *destory = curr->next;
            curr->next = curr->next->next;
            free(destory);
            destory = NULL;
        } else {
            curr = curr->next;
        }
    }
    return head;
}