# Remove Linked List Elements
**Difficulty:** EASY
[External](https://leetcode.com/problems/remove-linked-list-elements)
Canonical: https://scaleengineer.com/dsa/problems/remove-linked-list-elements
**Patterns:** [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
**Data structures:** Linked List
**Companies:** [Arista Networks](https://scaleengineer.com/companies/arista-networks)
---
## Problem
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:**

![](https://assets.glich.co/dsa/remove-linked-list-elements/image0.jpg) 

**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`

# Approaches
## Iterative Approach with Dummy Node
This approach uses a dummy node to simplify the logic of removing nodes from the linked list. By creating a dummy node that points to the head, we can handle the edge case where the head itself needs to be removed without special handling.
**Time:** O(n) · **Space:** O(1)
**Pros:** Simple and intuitive logic; Handles edge cases (empty list, removing head) elegantly; Single pass through the list; Easy to understand and implement
**Cons:** Uses extra dummy node (minimal overhead); Slightly more memory usage due to dummy node
### Explanation
We create a dummy node that points to the head of the linked list. This allows us to treat all nodes uniformly, including the head node. We then iterate through the list with two pointers: `prev` (starting at dummy) and `current` (starting at head). When we find a node with the target value, we skip it by updating `prev.next` to point to `current.next`. Otherwise, we move `prev` forward. Finally, we return `dummy.next` as the new head.

```java
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public ListNode removeElements(ListNode head, int val) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;
    ListNode current = head;
    
    while (current != null) {
        if (current.val == val) {
            prev.next = current.next;
        } else {
            prev = current;
        }
        current = current.next;
    }
    
    return dummy.next;
}
```
### Algorithm
1. Create a dummy node and point it to the head
2. Initialize `prev` pointer to dummy and `current` pointer to head
3. While `current` is not null:
   - If `current.val` equals target value:
     - Skip current node by setting `prev.next = current.next`
   - Else:
     - Move `prev` to `current`
   - Move `current` to `current.next`
4. Return `dummy.next` as the new head

## Iterative Approach without Dummy Node
This approach handles the removal of nodes without using a dummy node. It requires special handling for the head node since we need to update the head reference when removing nodes from the beginning of the list.
**Time:** O(n) · **Space:** O(1)
**Pros:** No extra dummy node needed; Slightly better space efficiency; Single pass through the list; Direct manipulation of the original list
**Cons:** More complex logic due to special head handling; Requires separate handling for head node removal; More prone to edge case bugs
### Explanation
First, we handle the special case where consecutive nodes at the beginning (including head) need to be removed. We keep moving the head pointer forward until we find a node that doesn't match the target value or reach the end. Then, we use two pointers to traverse the rest of the list: `prev` and `current`. When we find a node to remove, we update `prev.next` to skip the current node.

```java
public ListNode removeElements(ListNode head, int val) {
    // Handle nodes at the beginning that need to be removed
    while (head != null && head.val == val) {
        head = head.next;
    }
    
    // If list becomes empty
    if (head == null) {
        return null;
    }
    
    ListNode prev = head;
    ListNode current = head.next;
    
    while (current != null) {
        if (current.val == val) {
            prev.next = current.next;
        } else {
            prev = current;
        }
        current = current.next;
    }
    
    return head;
}
```
### Algorithm
1. Remove all nodes from the beginning that match the target value
2. If list becomes empty, return null
3. Initialize `prev` to head and `current` to head.next
4. While `current` is not null:
   - If `current.val` equals target value:
     - Skip current node by setting `prev.next = current.next`
   - Else:
     - Move `prev` to `current`
   - Move `current` to `current.next`
5. Return the updated head

## Recursive Approach
This approach uses recursion to solve the problem. The idea is to recursively process the rest of the list first, then decide whether to include the current node in the result based on its value.
**Time:** O(n) · **Space:** O(n)
**Pros:** Clean and elegant code; Natural handling of edge cases; No need for explicit pointer manipulation; Conceptually simple once you understand recursion
**Cons:** Uses O(n) extra space due to recursion stack; May cause stack overflow for very long lists; Less efficient in terms of space complexity; Harder to debug for beginners
### Explanation
The recursive approach works by first recursively calling the function on the next node to get the processed tail of the list. Then, we check if the current node's value matches the target value. If it matches, we return the processed tail (effectively removing the current node). If it doesn't match, we connect the current node to the processed tail and return the current node.

```java
public ListNode removeElements(ListNode head, int val) {
    // Base case: empty list
    if (head == null) {
        return null;
    }
    
    // Recursively process the rest of the list
    head.next = removeElements(head.next, val);
    
    // If current node should be removed, return the processed tail
    // Otherwise, return current node connected to processed tail
    return head.val == val ? head.next : head;
}
```
### Algorithm
1. Base case: if head is null, return null
2. Recursively call removeElements on head.next
3. Set head.next to the result of recursive call
4. If head.val equals target value:
   - Return head.next (skip current node)
5. Else:
   - Return head (keep current node)

# Solutions
### CSharp

```csharp
public class Solution { public ListNode RemoveElements ( ListNode head , int val ) { ListNode newHead = null ; ListNode newTail = null ; var current = head ; while ( current != null ) { if ( current . val != val ) { if ( newHead == null ) { newHead = newTail = current ; } else { newTail . next = current ; newTail = current ; } } current = current . next ; } if ( newTail != null ) newTail . next = null ; return newHead ; } }
```

### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode removeElements ( ListNode head , int val ) { ListNode dummy = new ListNode (- 1 , head ); ListNode pre = dummy ; while ( pre . next != null ) { if ( pre . next . val != val ) pre = pre . next ; else pre . next = pre . next . next ; } return dummy . next ; } }
```

### CPP

```cpp
class Solution { public: ListNode * removeElements ( ListNode * head , int val ) { ListNode * dummy = new ListNode (); dummy -> next = head ; ListNode * p = dummy ; while ( p -> next ) { if ( p -> next -> val == val ) { p -> next = p -> next -> next ; } else { p = p -> next ; } } return dummy -> next ; } };
```

### Python

```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 : ListNode , val : int ) -> ListNode : dummy = ListNode ( - 1 , head ) pre = dummy while pre . next : if pre . next . val != val : pre = pre . next else : pre . next = pre . next . next return dummy . next
```