Domain 1EasyCORE

Remove Linked List Elements

The problem requires removing all nodes from a singly linked list that have a specific value `val`. The input is the head of the linked list and the integer `val` to be removed. The output should be the new head of the modified linked list after removing all nodes with the given value.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Linked List

203. Remove Linked List Elements

Model: qwen2.5-coder:14b
Topics: Linked List
FAANG asked: 1
Acceptance rate: 39.5%


Problem Breakdown

The problem requires removing all nodes from a singly linked list that have a specific value val. The input is the head of the linked list and the integer val to be removed. The output should be the new head of the modified linked list after removing all nodes with the given value.

Inputs:

  • head: The head node of the singly linked list.
  • val: An integer representing the value of nodes to be removed.

Outputs:

  • The head node of the modified linked list.

Implicit Constraints and Edge Cases:

  1. Empty List: If the input list is empty (head is None), the function should return None.
  2. All Nodes with Target Value: If all nodes in the list have the value val, the function should return an empty list.
  3. Nodes at the Beginning/End/Middle: The node to be removed could be at the beginning, end, or middle of the list.

Intuition

A brute-force approach would involve iterating through the linked list and removing nodes with the target value by adjusting pointers. However, this approach can be inefficient if multiple consecutive nodes need to be removed, as it may require multiple pointer adjustments for each node.

The key insight is to use a dummy node that points to the head of the list. This allows us to handle edge cases where the head itself needs to be removed without special handling. By iterating through the list with a single pass and adjusting pointers appropriately, we can efficiently remove all nodes with the target value.

Approach

  1. Create a Dummy Node: Initialize a dummy node that points to the head of the list. This helps in easily removing the head if it needs to be deleted.
  2. Initialize a Pointer: Use a pointer current starting from the dummy node.
  3. Iterate Through the List: Traverse the linked list using the current pointer.
  4. Remove Nodes with Target Value:
    • If the next node’s value is equal to val, skip it by adjusting the next pointer of the current node to point to the node after the next node.
    • Otherwise, move the current pointer one step forward.
  5. Return the New Head: After processing all nodes, return the next node of the dummy node as the new head of the list.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the linked list. We traverse each node once.
  • Space Complexity: O(1). We use a constant amount of extra space for the dummy node and pointers.

Solution

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

def removeElements(head: ListNode, val: int) -> ListNode:
    # Create a dummy node that points to the head of the list
    dummy = ListNode(0)
    dummy.next = head
    
    # Initialize a pointer starting from the dummy node
    current = dummy
    
    # Iterate through the linked list
    while current.next:
        if current.next.val == val:
            # Skip the node with the target value
            current.next = current.next.next
        else:
            # Move to the next node
            current = current.next
    
    # Return the new head of the modified list
    return dummy.next

Edge Cases Handled

  • Empty List: If head is None, the function returns None.
  • All Nodes with Target Value: The dummy node ensures that if all nodes have the target value, the function returns an empty list.
  • Nodes at the Beginning/End/Middle: The approach handles nodes to be removed at any position in the list without special cases.