Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Examples

Example 1:

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

Example 2:

Input: head = [], val = 1
Output: []

Example 3:

Input: head = [7,7,7,7], val = 7
Output: []

Constraints

  • The number of nodes in the list is in the range [0, 10^4].
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

Thinking Process

  1. Dummy Node: Using a dummy node simplifies edge cases, especially when the head needs to be removed
  • Draw pointers before rewriting links.
  • Dummy head simplifies insert/delete at the head.
  • Slow/fast pointers find middle or detect cycles in one pass.
Two pointers 1 3 5 7 9 L R move L/R based on comparison

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Iterative pointer walk (this problem) O(n) O(1) Traversal, insertion
Dummy head node O(n) O(1) Simplify head-edge cases
Reversal (3-pointer) O(n) O(1) Reverse sublist or full list
Slow/fast pointers O(n) O(1) Middle, cycle, merge lists

Solution

Time Complexity: O(n) - We visit each node once
Space Complexity: O(1) - Only using constant extra space

The key insight is to use a dummy node to handle edge cases where the head itself needs to be removed. We traverse the list with two pointers: prev (previous node) and curr (current node), removing nodes that match the target value.

Solution: Iterative with Dummy Node

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() { this.val = 0; this.next = null; }
 *     ListNode(int x) { this.val = x; this.next = null; }
 *     ListNode(int x, ListNode next) { this.val = x; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null) return head;

        ListNode dummy = ListNode(0, head);
        ListNode prev = &dummy;
        ListNode curr = head;
        ListNode toDelete = null;

        while(curr != null) {
            if (curr.val == val) {
                prev.next = curr.next;
                toDelete = curr;
            } else {
                prev = curr;
            }
            curr = curr.next;

            if(toDelete != null) {
                delete toDelete;
                toDelete = null;
            }
        }

        ListNode ret = dummy.next;
        return ret;
    }
}

Solution Explanation

Approach: Iterative pointer walk (this problem)

Key idea: 1. Dummy Node: Using a dummy node simplifies edge cases, especially when the head needs to be removed

How the code works:

  1. Dummy Node: Using a dummy node simplifies edge cases, especially when the head needs to be removed
    • Draw pointers before rewriting links.
    • Dummy head simplifies insert/delete at the head.
    • Slow/fast pointers find middle or detect cycles in one pass.

Walkthrough — input head = [1,2,6,3,4,5,6], val = 6, expected output [1,2,3,4,5]:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

| Approach | Time | Space | Pros | Cons | |———-|——|——-|——|——| | Iterative with Dummy | O(n) | O(1) | Space efficient, handles all cases | Requires memory management | | Recursive | O(n) | O(n) | Elegant, concise | Stack overflow risk for long lists | | Simplified Iterative | O(n) | O(1) | Simple, no memory management | Doesn’t free memory (fine for LeetCode) |

Algorithm Breakdown

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null) return head;

        head.next = removeElements(head.next, val);

        return head.val == val ? head.next : head;
    }
}

Common Mistakes

  1. Empty list: head = [] → return []
  2. Head needs removal: head = [7,7,7,7], val = 7 → return []
  3. All nodes removed: head = [1,1,1], val = 1 → return []
  4. No nodes removed: head = [1,2,3], val = 4 → return [1,2,3]

  5. Remove from middle: head = [1,2,3,2,4], val = 2 → return [1,3,4]

  6. Not using dummy node: Makes it harder to handle head removal
  7. Incorrect pointer updates: Forgetting to update prev only when keeping a node
  8. Memory leaks: Not deleting removed nodes
  9. Returning wrong pointer: Should return dummy.next, not head
  10. Null pointer dereference: Not checking if head is nullptr first

Complexity

| Approach | Time | Space | Pros | Cons | |———-|——|——-|——|——| | Iterative with Dummy | O(n) | O(1) | Space efficient, handles all cases | Requires memory management | | Recursive | O(n) | O(n) | Elegant, concise | Stack overflow risk for long lists | | Simplified Iterative | O(n) | O(1) | Simple, no memory management | Doesn’t free memory (fine for LeetCode) |

Optimization Notes

  1. Dummy Node Pattern: Essential for simplifying linked list deletion problems
  2. Memory Management: In production code, always delete removed nodes
  3. Early Termination: Could optimize by checking if list is empty first
  4. Pointer Safety: Always check for nullptr before dereferencing

Key Takeaways

  1. Dummy Node: Using a dummy node simplifies edge cases, especially when the head needs to be removed
  2. Two Pointers: prev tracks the previous valid node, curr traverses the list
  3. Memory Management: Properly delete removed nodes to prevent memory leaks
  4. Pointer Updates: Only update prev when we don’t remove a node; otherwise, prev stays the same

References

Template Reference