Remove Linked List Elements - Mastering Pointer Manipulation

The Remove Linked List Elements problem is a fundamental linked list manipulation challenge that teaches essential pointer handling techniques. This problem is excellent for understanding when and why to use dummy nodes in linked list operations.

Problem Statement

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.

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: []

ListNode Definition

public class ListNode {
    int val;
    ListNode next;

    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

Solution Strategies

Approach 1: Dummy Node (Recommended)

Using a dummy node simplifies edge case handling and makes the code more uniform:

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // Create dummy node to simplify edge cases
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prev = dummy;
        ListNode current = head;

        while (current != null) {
            if (current.val == val) {
                // Skip the current node
                prev.next = current.next;
            } else {
                // Move prev pointer forward
                prev = current;
            }
            current = current.next;
        }

        return dummy.next;
    }
}

Time Complexity: O(n) - traverse list once Space Complexity: O(1) - only use constant extra space

Approach 2: Without Dummy Node

Handle the head removal case separately:

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // Remove elements from the beginning
        while (head != null && head.val == val) {
            head = head.next;
        }

        // If list becomes empty
        if (head == null) {
            return null;
        }

        ListNode current = head;

        // Remove elements from the middle and end
        while (current.next != null) {
            if (current.next.val == val) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }

        return head;
    }
}

Time Complexity: O(n) Space Complexity: O(1)

Approach 3: Recursive Solution

Leverage recursion to handle the removal elegantly:

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

        // Recursively process the rest of the list
        head.next = removeElements(head.next, val);

        // Return head if it should be kept, otherwise return head.next
        return head.val == val ? head.next : head;
    }
}

Time Complexity: O(n) Space Complexity: O(n) - recursion stack depth

Visual Walkthrough

Let's trace through the dummy node approach with head = [1,2,6,3,4,5,6] and val = 6:

Initial:     dummy -> 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 -> null
             prev     current

Step 1:      dummy -> 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 -> null
             prev          current (1 ≠ 6, move prev)

Step 2:      dummy -> 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 -> null
                      prev     current (2 ≠ 6, move prev)

Step 3:      dummy -> 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 -> null
                           prev  current (6 = 6, skip node)
After skip: dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
                           prev  current

Step 4:      dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
                           prev       current (3 ≠ 6, move prev)

...continue until end...

Final:       dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null

Key Insights

Why Use a Dummy Node?

1. Uniform Handling: No special case for removing the head node
2. Simplified Logic: Always have a previous node to update
3. Cleaner Code: Reduces conditional branches and potential bugs
4. Edge Case Safety: Handles empty lists and single-element lists gracefully

Common Pitfalls

1. Memory Leaks: In languages with manual memory management, don't forget to free removed nodes
2. Null Pointer Exceptions: Always check if nodes exist before accessing their properties
3. Head Updates: When not using dummy nodes, remember to update the head reference
4. Infinite Loops: Ensure you advance pointers correctly to avoid infinite loops

Comparison of Approaches

Approach	Pros	Cons	Best Use Case
Dummy Node	Uniform logic, fewer edge cases	Extra node creation	General purpose, interviews
Without Dummy	No extra space	Complex head handling	Memory-constrained environments
Recursive	Elegant, functional style	Stack overflow risk, extra space	Educational, functional programming

Related Problems and Patterns

1. Remove Duplicates from Sorted List: Similar pointer manipulation
2. Merge Two Sorted Lists: Uses dummy node pattern
3. Reverse Linked List: Fundamental pointer operations
4. Delete Node in a Linked List: Different removal scenario

Advanced Considerations

Performance Optimizations

For very large lists with many removals:

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // Early termination if all nodes need removal
        if (head == null) return null;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode current = head;

        while (current != null) {
            if (current.val == val) {
                // Batch remove consecutive elements
                while (current != null && current.val == val) {
                    current = current.next;
                }
                prev.next = current;
            } else {
                prev = current;
                current = current.next;
            }
        }

        return dummy.next;
    }
}

Conclusion

The Remove Linked List Elements problem demonstrates essential linked list manipulation techniques. The dummy node approach is generally preferred for its simplicity and robustness against edge cases.

Key takeaways:

• Dummy nodes simplify linked list manipulation
• Pointer management is crucial for correct list operations
• Edge cases (empty lists, single elements) must be carefully considered
• Multiple approaches exist, each with different trade-offs

This problem serves as an excellent foundation for more complex linked list algorithms and is frequently used in technical interviews to assess pointer manipulation skills.