203. Remove Linked List Elements - Explanation

Description

You are 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 = [2,1,4,1,2,3], val = 2

Output: [1,4,1,3]

Example 2:

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

Output: []

Constraints:

0 <= Length of the list <= 10,000.
1 <= Node.val <= 50
0 <= val <= 50

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

A straightforward approach is to extract all values we want to keep into an array, then build a new linked list from scratch.
We traverse the original list, skipping nodes with the target value, and collect the remaining values.
Finally, we create new nodes from this array and link them together.
This works but requires extra space and creates entirely new nodes.

Algorithm

Traverse the linked list and collect all node values that are not equal to val into an array.
If the array is empty, return null.
Create a new linked list by making nodes from each value in the array.
Return the head of the new list.

# 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]:
        arr = []
        cur = head

        while cur:
            if cur.val != val:
                arr.append(cur.val)
            cur = cur.next

        if not arr:
            return None

        res = ListNode(arr[0])
        cur = res
        for i in range(1, len(arr)):
            node = ListNode(arr[i])
            cur.next = node
            cur = cur.next

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Recursion

Intuition

Recursion naturally fits linked list problems because each node is structurally similar to the rest of the list.
We recursively process the remainder of the list first, then decide whether to include the current node.
If the current node matches the target value, we skip it by returning the already-processed next portion.
Otherwise, we attach the current node to the processed tail and return it.

Algorithm

Base case: if the list is empty, return null.
Recursively call the function on head.next to process the rest of the list.
Attach the result to head.next.
If head.val equals val, return head.next to skip the current node; otherwise return head.

# 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 not head:
            return None
        head.next = self.removeElements(head.next, val)
        return head if head.val != val else head.next

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

3. Iteration

Intuition

To remove nodes in place without recursion, we use a dummy node to handle edge cases like removing the head.
We maintain two pointers: prev (the last valid node) and curr (the node being examined).
When we find a matching value, we bypass the current node by updating prev.next.
When the value does not match, we simply advance prev.

Algorithm

Create a dummy node pointing to head.
Initialize prev to the dummy node and curr to head.
While curr is not null:
- If curr.val equals val, set prev.next to curr.next to skip the current node.
- Otherwise, move prev to curr.
- Move curr to the next node.
Return dummy.next.

# 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(0, head)
        prev, curr = dummy, head

        while curr:
            nxt = curr.next
            if curr.val == val:
                prev.next = nxt
            else:
                prev = curr
            curr = nxt

        return dummy.next

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

4. Iteration Without Prev Pointer

Intuition

We can simplify the iteration by always looking ahead at the next node instead of the current one.
By checking curr.next rather than curr, we can remove nodes without needing a separate prev pointer.
If the next node should be removed, we skip it by updating curr.next directly.
Otherwise, we advance curr to continue scanning.

Algorithm

Create a dummy node pointing to head.
Set curr to the dummy node.
While curr.next is not null:
- If curr.next.val equals val, set curr.next to curr.next.next to remove the node.
- Otherwise, advance curr to curr.next.
Return dummy.next.

# 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)
        curr = dummy

        while curr.next:
            if curr.next.val == val:
                curr.next = curr.next.next
            else:
                curr = curr.next

        return dummy.next

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Not Handling Head Node Removal

When the head node itself contains the target value, returning head without adjustment results in incorrect output. This is why a dummy node pointing to the head is essential. The dummy node acts as a stable anchor, and returning dummy.next correctly handles cases where the original head is removed.

Advancing the Pointer After Removal

When removing a node, a common mistake is advancing curr or prev immediately after the deletion. If you move curr forward after setting prev.next = curr.next, you skip the node that was just moved into position and may miss consecutive nodes with the target value. Only advance the pointer when no removal occurs; otherwise, keep it in place to check the newly linked node.