Problem Description

You are given the head of a singly linked list and an integer value val. Your task is to remove all nodes from the linked list that have a value equal to val and return the head of the modified linked list.

The problem requires you to traverse through the linked list and delete every node whose value matches the given target value. After removing all such nodes, you need to return the new head of the list (which might be different from the original head if the original head node itself needs to be removed).

For example:

• If the linked list is 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 and val = 6, the result should be 1 -> 2 -> 3 -> 4 -> 5
• If the linked list is 7 -> 7 -> 7 -> 7 and val = 7, the result should be an empty list (return null)

The solution uses a dummy node technique to handle edge cases where the head node itself needs to be removed. By creating a dummy node that points to the original head, we can treat all nodes uniformly without special handling for the head node. The algorithm maintains a pre pointer that checks the next node's value. If the next node's value equals val, it skips that node by adjusting the link (pre.next = pre.next.next). Otherwise, it moves the pre pointer forward. Finally, it returns dummy.next, which is the new head of the modified list.

Intuition

When removing nodes from a linked list, the main challenge is maintaining proper connections between the remaining nodes. We need to "skip over" the nodes we want to remove by redirecting pointers.

The key insight is that to remove a node, we need access to the node before it. This is because in a singly linked list, we can only modify the next pointer of a node to skip over unwanted nodes. If we're at node A and want to remove node B (where A points to B), we simply make A point to C instead (where B was pointing to C).

However, this creates a special case problem: what if the head node itself needs to be removed? We don't have a previous node to work with. We could handle this with special conditional logic, checking if the head matches the target value and updating it separately. But this leads to messy code with multiple cases.

The elegant solution is to use a dummy node. By creating a temporary node that points to the head, we artificially create a "previous node" for the head. Now every node in the original list, including the head, has a predecessor. This uniform structure allows us to use the same removal logic for all nodes without special cases.

We maintain a pointer pre that always stays one step behind the node we're examining. At each step, we check pre.next.val:

• If it matches our target value, we skip it by setting pre.next = pre.next.next
• If it doesn't match, we advance pre to pre.next

This way, pre always stays on a "safe" node (one we're keeping), and we can safely manipulate its next pointer to remove unwanted nodes. After processing the entire list, dummy.next gives us the new head of the cleaned list.

Solution Approach

The implementation uses a dummy node pattern to simplify the linked list manipulation. Here's the step-by-step breakdown:

1. Create a Dummy Node:

   dummy = ListNode(-1, head)

   We create a dummy node with an arbitrary value (-1) that points to the original head. This dummy node serves as a stable reference point and handles the edge case where the head itself needs to be removed.

2. Initialize the Traversal Pointer:

   pre = dummy

   We set pre to start at the dummy node. This pointer will always stay one node behind the node we're examining, allowing us to modify connections.

3. Traverse the List:

   while pre.next:

   We continue traversing as long as there's a next node to examine. Note that we check pre.next instead of pre because we need to look ahead to decide whether to remove the next node.

4. Check and Remove Nodes:

   if pre.next.val != val:
       pre = pre.next
   else:
       pre.next = pre.next.next

   • If the next node's value doesn't match val, we keep it and move pre forward
   • If the next node's value matches val, we remove it by bypassing it: pre.next now points to pre.next.next, effectively removing the node from the chain
   • Notice that when we remove a node, we don't move pre forward because we need to check the new pre.next in the next iteration

5. Return the New Head:

   return dummy.next

   After processing all nodes, dummy.next points to the new head of the modified list. This could be the original head (if it wasn't removed) or a different node (if the original head was removed).

Time Complexity: O(n) where n is the number of nodes in the linked list, as we visit each node exactly once.

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

Example Walkthrough

Let's walk through a concrete example to see how the algorithm works step by step.

Example: Remove all nodes with value 2 from the linked list 1 -> 2 -> 2 -> 3 -> 2 -> 4

Initial Setup:

dummy(-1) -> 1 -> 2 -> 2 -> 3 -> 2 -> 4
pre = dummy

Step 1: Check pre.next.val (which is 1)

• 1 ≠ 2, so move pre forward

dummy(-1) -> 1 -> 2 -> 2 -> 3 -> 2 -> 4
             pre

Step 2: Check pre.next.val (which is 2)

• 2 = 2, so remove this node by setting pre.next = pre.next.next

dummy(-1) -> 1 -----> 2 -> 3 -> 2 -> 4
             pre

Step 3: Check pre.next.val (which is still 2)

• 2 = 2, so remove this node again

dummy(-1) -> 1 -----------> 3 -> 2 -> 4
             pre

Step 4: Check pre.next.val (which is 3)

• 3 ≠ 2, so move pre forward

dummy(-1) -> 1 -> 3 -> 2 -> 4
                  pre

Step 5: Check pre.next.val (which is 2)

• 2 = 2, so remove this node

dummy(-1) -> 1 -> 3 -----> 4
                  pre

Step 6: Check pre.next.val (which is 4)

• 4 ≠ 2, so move pre forward

dummy(-1) -> 1 -> 3 -> 4
                       pre

Step 7: pre.next is null, so we're done

Result: Return dummy.next, which points to the head of the modified list: 1 -> 3 -> 4

Notice how the dummy node allowed us to handle all removals uniformly, even if we had needed to remove the first node. The key insight is that pre stays on "safe" nodes we're keeping, while we look ahead to decide whether to skip the next node.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list. The algorithm traverses the linked list once using a single while loop. In each iteration, it either moves the pointer forward or removes a node, but each node is visited at most once. Therefore, the time complexity is linear.

Space Complexity: O(1). The algorithm only uses a constant amount of extra space regardless of the input size. It creates a dummy node and uses two pointer variables (dummy and pre), which occupy constant space. The removal operation is done in-place by modifying the pointers of the existing nodes without creating any new nodes or using additional data structures that scale with input size.

Common Pitfalls

1. Forgetting to Handle Head Removal

One of the most common mistakes is trying to handle the linked list without considering that the head node itself might need to be removed. This leads to complex conditional logic and potential bugs.

Incorrect Approach:

def removeElements(self, head: ListNode, val: int) -> ListNode:
    # This fails when all leading nodes need to be removed
    current = head
    while current and current.next:
        if current.next.val == val:
            current.next = current.next.next
        else:
            current = current.next
  
    # Doesn't handle if head.val == val
    return head

Solution: Always use a dummy node to uniformly handle all nodes including the head.

2. Moving the Pointer After Deletion

A critical mistake is advancing the previous pointer after removing a node. When you remove a node, the previous.next already points to a new node that hasn't been checked yet.

Incorrect Approach:

while previous.next:
    if previous.next.val == val:
        previous.next = previous.next.next
        previous = previous.next  # WRONG! This skips checking the new next node
    else:
        previous = previous.next

Solution: Only move the pointer forward when you're NOT removing a node. After removal, stay at the same position to check the new next node.

3. Not Checking for None Before Accessing next.next

When removing a node, accessing previous.next.next without ensuring it exists can cause AttributeError.

Incorrect Approach:

while previous.next:
    if previous.next.val == val:
        # Dangerous if previous.next is the last node
        previous.next = previous.next.next  # previous.next.next might be None

Solution: The code actually handles this correctly because when previous.next.next is None, it's valid to assign None to previous.next, which properly terminates the list.

4. Using current Instead of previous Pointer

Some implementations try to use a current pointer to traverse, which makes it impossible to remove the current node since you've lost the reference to the previous node.

Incorrect Approach:

current = head
while current:
    if current.val == val:
        # Can't remove current without access to previous node!
        pass
    current = current.next

Solution: Always maintain a pointer to the node BEFORE the one you might need to remove, allowing you to update the links properly.