Remove Linked List Elements

---

Remove Linked List Elements: 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

---

Try this Problem on your own or check similar problems:

1. Remove Element
2. Delete Node in a Linked List
3. Delete the Middle Node of a Linked List

Solution:

Java

public ListNode removeElements(ListNode head, int val) {
    if (head == null) return null;

    ListNode dummy = new ListNode(-1, head), curr = dummy;

    while(curr.next != null){
        if(curr.next.val == val){
            curr.next = curr.next.next;
        }
        else{
            curr = curr.next;
        }
    }

    return dummy.next;
}

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function (head, val) {
  if (head === null) {
    return null;
  }

  let dummy = new ListNode(-1, head);
  let curr = dummy;

  while (curr.next !== null) {
    if (curr.next.val === val) {
      curr.next = curr.next.next;
    } else {
      curr = curr.next;
    }
  }

  return dummy.next;
};

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        if head is None:
            return None

        dummy = ListNode(-1, head)
        curr = dummy

        while curr.next is not None:
            if curr.next.val == val:
                curr.next = curr.next.next
            else:
                curr = curr.next

        return dummy.next

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (head == nullptr) return nullptr;

        ListNode* dummy = new ListNode(-1, head);
        ListNode* curr = dummy;

        while (curr->next != nullptr) {
            if (curr->next->val == val) {
                ListNode* temp = curr->next;
                curr->next = temp->next;
                delete temp;
            } else {
                curr = curr->next;
            }
        }

        return dummy->next;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

The dummy node is called sentinel, and you will see it many linked list problems, it's an artificial node holding no real value ("real" in context of linked list values) and pointing to the head of the list (or the end). Why do we need it? Well, it comes in handy when we must remove the head of the linked list (head node has value equal to val). So, we define the dummy node with also curr which will serve as our list iterator. We iterate through the list and we're checking if curr.next != null instead of curr != null. You could do it with curr != null, but then you would need a prev pointer, so you can relink if the curr node has value of val. So everytime we face next element with value val we "skip it" by relinking to the next node after it, otherwise we just move the iterator to the next node that contains different value than val. Dummy node will be pointing to the new head so we just have to return dummy.next. We're iterating over the list with n nodes so we have linear time complexity.