Leetcode 203. Remove Linked List Elements

Problem

Given the head of a singly linked list and an integer value, remove all nodes from the linked list that have a node value equal to the given value. Return the head of the modified linked list.

The linked list may contain multiple occurrences of the target value, including at the beginning, middle, or end of the list. All occurrences should be removed.

Requirements

1. Remove all nodes whose value matches the target value
2. Maintain the relative order of remaining nodes
3. Return the head of the modified list
4. Handle cases where the head node(s) need to be removed
5. Handle empty lists appropriately

Constraints

• The number of nodes in the list is in the range [0, 10000]
• 1 ≤ Node.val ≤ 50
• 0 ≤ val ≤ 50
• The solution should run in O(n) time where n is the number of nodes
• Use O(1) extra space (not counting the output)

Examples

Example 1:

Input: head = [1, 2, 6, 3, 4, 5, 6], val = 6 Output: [1, 2, 3, 4, 5] Explanation: Both nodes with value 6 are removed from the list

Example 2:

Input: head = [7, 7, 7, 7], val = 7 Output: [] Explanation: All nodes have value 7, so the resulting list is empty

Example 3:

Input: head = [], val = 1 Output: [] Explanation: The list is already empty

Example 4:

Input: head = [1, 2, 3, 4], val = 5 Output: [1, 2, 3, 4] Explanation: No nodes have value 5, so the list remains unchanged

Hint 1: Using a Dummy Node Consider using a dummy node before the head. This simplifies handling the case where the head itself needs to be removed, as you won't need special logic for the first node.

Hint 2: Two Pointer Technique Use two pointers: one to track the current node being examined and another to track the previous node. This allows you to easily bypass nodes that need to be removed by adjusting the next pointer of the previous node.

Hint 3: Edge Cases Pay special attention to:

• Empty lists (null head)
• All nodes matching the target value
• Consecutive nodes at the beginning matching the target
• Only the last node matching the target

Full 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 pointing to head # This simplifies handling removal of head nodes dummy = ListNode(0) dummy.next = head

# Use current pointer to traverse the list
current = dummy

# Iterate through the list
while current.next:
    if current.next.val == val:
        # Skip the node with matching value
        current.next = current.next.next
    else:
        # Move to next node only if no deletion occurred
        current = current.next

# Return the new head (which may have changed)
return dummy.next

`

Approach Explanation:

The solution uses a dummy node technique combined with a single-pass traversal:

1. Dummy Node: We create a dummy node that points to the head. This eliminates special case handling for when the head node itself needs to be removed.

2. Traversal: We maintain a current pointer starting at the dummy node. We examine current.next in each iteration.

3. Deletion Logic:

   • If current.next.val equals the target value, we bypass that node by setting current.next = current.next.next
   • If the value doesn't match, we advance current to current.next

4. Key Insight: We don't advance the current pointer after a deletion because current.next now points to a new node that also needs to be checked.

Time Complexity: O(n) where n is the number of nodes in the list. We traverse the list exactly once.

Space Complexity: O(1) as we only use a constant amount of extra space (dummy node and pointer variables).