Remove Linked List Elements

How it works

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.

Steps

1. Create a dummy node pointing to head.
2. Set curr to the dummy node.
3. 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.
4. Return dummy.next.

Complexity

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

Things to watch for

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.

# 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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode dummy(-1, head);
        ListNode *curr = &dummy;

        while (curr->next) {
            if (curr->next->val == val) {
                curr->next = curr->next->next;
            } else {
                curr = curr->next;
            }
        }

        return dummy.next;
    }
};