Code Implementation

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(0)
        dummy.next = head
        current = dummy
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
            else:
                current = current.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(0);
        dummy.next = head;
        ListNode* current = &dummy;
        while (current->next) {
            if (current->next->val == val) {
                current->next = current->next->next;
            } else {
                current = current->next;
            }
        }
        return dummy.next;
    }
};
      

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;
        while (current.next != null) {
            if (current.next.val == val) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
        return dummy.next;
    }
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    let dummy = new ListNode(0, head);
    let current = dummy;
    while (current.next) {
        if (current.next.val === val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    return dummy.next;
};
      

Problem Description

Given the head of a singly linked list and an integer val, remove all the nodes of the linked list that have val as their value, and return the new head of the linked list.

• Each node in the list contains an integer value and a pointer to the next node.
• There may be zero or more nodes with the value val to remove.
• You must not create new nodes for the remaining elements; reuse the existing nodes.
• There is always at least one valid solution (possibly an empty list).

Thought Process

The core of this problem is about traversing a singly linked list and removing nodes that match a given value. A naive approach might involve creating a new list and copying only the nodes that don't match val, but the problem specifically asks us to reuse the original nodes.

If we try to remove nodes in place, we have to be careful with how we update pointers, especially when the head node itself needs to be removed. This suggests we need a way to handle edge cases, such as when the first node(s) have the target value.

To simplify pointer manipulation and avoid special cases for the head, we can use a "dummy" node that points to the head of the list. This dummy node makes it easier to remove nodes uniformly, including the head, by always looking at current.next rather than current itself.

Solution Approach

• Step 1: Create a Dummy Node
  Create a new node (dummy) whose next pointer points to the head of the original list. This helps in easily removing the head node if needed.
• Step 2: Initialize a Pointer
  Set a pointer (current) to start at the dummy node.
• Step 3: Traverse the List
  While current.next is not null, check if current.next.val equals val.
  • If it does, skip the node by setting current.next = current.next.next.
  • If it does not, move current forward by one node.
• Step 4: Return the Result
  After traversal, return dummy.next as the new head of the list.

This approach ensures all nodes with the target value are removed, including those at the head or in consecutive positions, without needing to handle special cases separately.

Example Walkthrough

Suppose the input linked list is: 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 and val = 6.

1. Create a dummy node: 0 -> 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6
2. Set current to dummy. Examine current.next:
   • current.next is 1 (not 6) → move current to 1
   • current.next is 2 (not 6) → move current to 2
   • current.next is 6 (matches 6) → remove it: 2 -> 3
   • current.next is 3 (not 6) → move current to 3
   • current.next is 4 (not 6) → move current to 4
   • current.next is 5 (not 6) → move current to 5
   • current.next is 6 (matches 6) → remove it: 5 -> null
3. The resulting list is 1 -> 2 -> 3 -> 4 -> 5.

Time and Space Complexity

• Brute-force Approach: Creating a new list and copying nodes would take O(n) time and O(n) space, where n is the number of nodes.
• Optimized Approach (In-place): The algorithm traverses each node once, so the time complexity is O(n). Only a constant amount of extra space is used (for the dummy node and pointers), so space complexity is O(1).

This efficiency is achieved because we only move pointers and do not allocate new nodes for the answer.

Summary

The problem is elegantly solved by using a dummy node to simplify pointer manipulation and avoid special cases when removing the head of the list. By traversing once and carefully updating pointers, we efficiently remove all nodes with the target value in O(n) time and O(1) space. This approach demonstrates the power of simple structural tricks (like dummy nodes) in linked list manipulation.