203

203. Remove Linked List Elements (Easy)

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, 104].
• 1 <= Node.val <= 50
• 0 <= val <= 50

Companies:
Facebook, Apple

Related Topics:
Linked List, Recursion

Similar Questions:

• Remove Element (Easy)
• Delete Node in a Linked List (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/remove-linked-list-elements/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode dummy, *tail = &dummy;
        while (head) {
            auto p = head;
            head = head->next;
            if (p->val == val) continue;
            tail->next = p;
            tail = p;
        }
        tail->next = NULL;
        return dummy.next;
    }
};

Or

// OJ: https://leetcode.com/problems/remove-linked-list-elements/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode dummy(0, head);
        for (auto p = &dummy; p && p->next;) {
            if (p->next->val != val) p = p->next;
            else p->next = p->next->next;
        }
        return dummy.next;
    }
};