LeetCode 203 - Remove Linked List Elements

The problem asks us to remove every node from a singly linked list whose value is equal to a given integer val. After all matching nodes are removed, we must return the head of the modified linked list.

leetcodeeasylinked-listrecursion

LeetCode Problem 203

Difficulty: 🟢 Easy
Topics: Linked List, Recursion

Solution

Problem Understanding

The problem asks us to remove every node from a singly linked list whose value is equal to a given integer val. After all matching nodes are removed, we must return the head of the modified linked list.

A linked list is a linear data structure where each node stores a value and a reference to the next node. Unlike arrays, linked lists do not support direct indexing, so modifications are usually performed by changing node pointers.

The input consists of two parts:

  • head, which points to the first node of the linked list
  • val, the integer value that should be removed from the list

The output should be the head of the updated linked list after all matching nodes have been deleted.

For example, if the list is:

1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6

and val = 6, then every node containing 6 must be removed, resulting in:

1 -> 2 -> 3 -> 4 -> 5

The constraints tell us several important things about the problem:

  • The list can contain up to 10^4 nodes, so the solution should ideally run in linear time.
  • Node values are small integers, but that does not significantly affect the algorithm design because we still need to inspect every node.
  • The list may be empty, which means head can be None in Python or nil in Go.

Several edge cases are especially important:

  • The list may be empty from the start.
  • All nodes may need to be removed.
  • The head node itself may need to be removed.
  • Multiple consecutive nodes may contain the target value.
  • No nodes may contain the target value.

A naive implementation often fails when the head node must be removed because deleting the first node changes the list's starting point. Proper pointer management is essential.

Approaches

A brute-force approach would repeatedly scan the linked list and remove one matching node at a time until no matching nodes remain. Each pass would traverse the list again, leading to unnecessary repeated work. While this method eventually produces the correct answer, it is inefficient because the same nodes may be visited many times.

A better solution comes from recognizing that we only need a single traversal. As we move through the list, we can immediately decide whether to keep or remove each node. The key challenge is safely handling removals at the beginning of the list. To simplify this, we use a dummy node placed before the actual head.

The dummy node acts as a stable predecessor for the head. This eliminates special-case logic when the first node must be deleted. During traversal, we examine current.next instead of current, allowing us to remove nodes by changing pointers without losing access to the rest of the list.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Repeatedly scans the list and removes one node at a time
Optimal O(n) O(1) Single traversal using pointer manipulation and a dummy node

Algorithm Walkthrough

  1. Create a dummy node whose next pointer references the original head of the list. This dummy node simplifies removal logic because every real node now has a predecessor, including the original head.
  2. Initialize a pointer called current to the dummy node. This pointer will move through the list and inspect the next node at each step.
  3. Traverse the list while current.next is not None. We inspect the next node rather than the current node because removal operations require access to the predecessor.
  4. If current.next.val == val, remove the node by skipping it:
current.next = current.next.next

This changes the pointer so the unwanted node is no longer connected to the list. 5. If the next node does not contain the target value, move current forward to continue traversal. 6. Continue until the end of the list is reached. 7. Return dummy.next, which points to the updated head of the modified list.

Why it works

The algorithm maintains the invariant that all nodes before current have already been processed correctly and contain no removable values. By always examining current.next, the algorithm can safely delete nodes without losing access to the remaining list. The dummy node guarantees that even the original head can be removed uniformly, so all cases are handled consistently.

Python Solution

# 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]:
        dummy = ListNode(0)
        dummy.next = head
        
        current = dummy
        
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
            else:
                current = current.next
        
        return dummy.next

The implementation begins by creating a dummy node and attaching it before the original head. This avoids special handling for head removal cases.

The current pointer starts at the dummy node. During traversal, the algorithm always checks current.next. This design is important because removing a node requires modifying the predecessor's next pointer.

When a matching node is found, the algorithm skips it by assigning:

current.next = current.next.next

This disconnects the unwanted node from the linked list.

If the node should remain in the list, the traversal pointer advances normally.

Finally, the method returns dummy.next, which points to the correct head after all removals are complete.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    dummy := &ListNode{Next: head}
    
    current := dummy
    
    for current.Next != nil {
        if current.Next.Val == val {
            current.Next = current.Next.Next
        } else {
            current = current.Next
        }
    }
    
    return dummy.Next
}

The Go implementation follows the same logic as the Python version. The primary difference is the use of pointers and nil instead of None.

The dummy node is created using:

dummy := &ListNode{Next: head}

Pointer manipulation works naturally in Go because linked lists are reference-based structures. No additional memory allocation is required beyond the dummy node.

There are no integer overflow concerns because the algorithm only performs pointer operations and comparisons.

Worked Examples

Example 1

Input:

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

Initial list:

dummy -> 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6
Step current current.next Action List State
1 dummy 1 Keep node 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6
2 1 2 Keep node 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6
3 2 6 Remove node 1 -> 2 -> 3 -> 4 -> 5 -> 6
4 2 3 Keep node 1 -> 2 -> 3 -> 4 -> 5 -> 6
5 3 4 Keep node 1 -> 2 -> 3 -> 4 -> 5 -> 6
6 4 5 Keep node 1 -> 2 -> 3 -> 4 -> 5 -> 6
7 5 6 Remove node 1 -> 2 -> 3 -> 4 -> 5

Final output:

[1,2,3,4,5]

Example 2

Input:

head = []
val = 1

Initial state:

dummy -> None

Since current.next is already None, the loop never executes.

Final output:

[]

Example 3

Input:

head = [7,7,7,7]
val = 7

Initial list:

dummy -> 7 -> 7 -> 7 -> 7
Step current current.next Action List State
1 dummy 7 Remove node 7 -> 7 -> 7
2 dummy 7 Remove node 7 -> 7
3 dummy 7 Remove node 7
4 dummy 7 Remove node empty

Final output:

[]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited at most once
Space O(1) Only a few pointer variables are used

The algorithm performs a single traversal through the linked list. Every node is inspected exactly once, so the running time grows linearly with the number of nodes.

The space complexity is constant because no auxiliary data structures proportional to the input size are allocated. The dummy node and traversal pointer require only fixed additional memory.

Test Cases

# Helper utilities for testing

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    current = dummy
    
    for value in values:
        current.next = ListNode(value)
        current = current.next
    
    return dummy.next

def to_list(head):
    result = []
    
    while head:
        result.append(head.val)
        head = head.next
    
    return result

class Solution:
    def removeElements(self, head, val):
        dummy = ListNode(0)
        dummy.next = head
        
        current = dummy
        
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
            else:
                current = current.next
        
        return dummy.next

solution = Solution()

# Provided examples
assert to_list(solution.removeElements(build_list([1,2,6,3,4,5,6]), 6)) == [1,2,3,4,5]  # remove multiple target nodes
assert to_list(solution.removeElements(build_list([]), 1)) == []  # empty list
assert to_list(solution.removeElements(build_list([7,7,7,7]), 7)) == []  # remove all nodes

# Boundary cases
assert to_list(solution.removeElements(build_list([1]), 1)) == []  # single node removed
assert to_list(solution.removeElements(build_list([1]), 2)) == [1]  # single node kept

# Consecutive removals
assert to_list(solution.removeElements(build_list([1,2,2,2,3]), 2)) == [1,3]  # consecutive middle removals

# Head removal cases
assert to_list(solution.removeElements(build_list([6,6,1,2]), 6)) == [1,2]  # remove leading nodes

# Tail removal cases
assert to_list(solution.removeElements(build_list([1,2,6,6]), 6)) == [1,2]  # remove trailing nodes

# No removals
assert to_list(solution.removeElements(build_list([1,2,3]), 4)) == [1,2,3]  # unchanged list

# Alternating removals
assert to_list(solution.removeElements(build_list([1,2,1,2,1]), 1)) == [2,2]  # alternating target nodes
Test Why
[1,2,6,3,4,5,6], val=6 Verifies normal removal behavior
[], val=1 Confirms empty list handling
[7,7,7,7], val=7 Ensures all nodes can be removed
[1], val=1 Tests single-node deletion
[1], val=2 Tests single-node preservation
[1,2,2,2,3], val=2 Verifies consecutive removals
[6,6,1,2], val=6 Ensures head removal works correctly
[1,2,6,6], val=6 Ensures tail removal works correctly
[1,2,3], val=4 Confirms unchanged list behavior
[1,2,1,2,1], val=1 Tests repeated alternating removals

Edge Cases

One important edge case occurs when the linked list is empty. A naive implementation may attempt to access head.val immediately, causing a null reference error. In this implementation, the traversal condition checks current.next before accessing any node fields, so an empty list safely returns None or nil.

Another critical case happens when the head node itself must be removed. Many incorrect solutions fail because they lose the reference to the new head after deletion. The dummy node solves this elegantly by ensuring there is always a stable predecessor before the actual head. Even if multiple leading nodes must be removed, the algorithm continues working correctly.

A third important case is when every node contains the target value. In such situations, repeated removals occur without advancing the traversal pointer. This behavior is intentional because after removing one node, the next node may also need removal. Eventually, all nodes are skipped, and dummy.next becomes None, correctly producing an empty list.