Solution: Remove Linked List Elements

Statement

You are given the head of a linked list and an integer k. Remove all nodes from the linked list where the node’s value equals k, and return the head of the updated list.

Constraints:

• The number of nodes in the list is in the range $[0, 10^3]$.

• $1 \leq$ Node.data $\leq 50$

• $0 \leq$ k $\leq 50$

Solution

The core intuition behind solving this problem is to modify the linked list in place. We create a dummy node to handle scenarios where the head node needs removal. Additionally, we use two pointers for traversal: one to keep track of the previous node and the other to track the current node. We iterate through the linked list and check if the current node’s data equals k. If it is, we remove this node from the linked list by updating the next link of the previous node. If the current node’s data doesn’t match k, we move both pointers forward to process the next nodes.

Using the above intuition, the solution can be implemented as follows:

1. Create a dummy node pointing to the head of the linked list. This helps us handle edge cases, like removing the head node, without needing special checks.

2. Initialize two pointers for traversal: prev starts at the dummy node, and curr starts at the head of the linked list.

3. Iterate through the linked list:

   1. If the curr node’s value matches k, we remove this node from the linked list by updating next of prev to next of curr. We also delete this node if needed. Then, we move curr to the next node.

   2. If the curr node’s value does not match k, move both prev and curr forward to process the next node.

4. After traversing the complete linked list, we return the updated list’s head stored in the next of the dummy node. We also delete the dummy node if need be.

Let’s look at the following illustration to get a better understanding of the solution: