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:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeElements(self, head, val):
        if head == None:
            return head

        dummy = ListNode(0, head)
        prev = dummy
        curr = head
        toDelete = None

        while curr != None:
            if curr.val == val:
                prev.next = curr.next
                toDelete = curr
            else:
                prev = curr

            curr = curr.next

            # Python does not need manual delete (kept for syntax consistency)
            if toDelete != None:
                toDelete = None

        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

def removeElements(self, head, val):
    # Handle empty list
    if(head == None) return head
    # Create dummy node to simplify edge cases
    def dummy(self, 0, head)
    ListNode prev = dummy  # Previous valid node
    ListNode curr = head    # Current node being checked
    ListNode toDelete = None
    while curr != None:
        if curr.val == val:
            # Skip the current node
            prev.next = curr.next
            toDelete = curr  # Mark for deletion
             else :
            # Move prev forward only when we keep the node
            prev = curr
        # Move to next node
        curr = curr.next
        # Delete removed node
        if toDelete != None:
            delete toDelete
            toDelete = None
    return dummy.next  # Return new 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