Solution: Deletion by Value

Let’s solve the Deletion by Value problem.

We'll cover the following

Statement

Given the head of a singly linked list and a value to be deleted from the linked list, if the value exists in the linked list, delete the value and return TRUE. Otherwise, return FALSE.

Constraints:

Let n be the number of nodes in the linked list:

  • 1≤1 \leq n ≤500\leq 500

  • −5000≤-5000 \leq Node.data ≤5000\leq 5000

Solution

We traverse the linked list, iterating through each node to find the one containing the specified value to be deleted. While traversing, we maintain references to both the current node and its preceding node. Once the node with the specified value is found, we update the reference of the preceding node to skip over the current node, effectively excluding it from the linked list. If the target value is not found during traversal, it implies its absence within the linked list. The algorithm returns a boolean value indicating whether the deletion was successful.

The steps of the algorithm are given below:

  1. Initialize a boolean variable, deleted, with FALSE to track whether the deletion is successful.

  2. Initialize a current pointer to the head of the linked list and a previous pointer to NULL.

  3. If current is pointing to the value to be deleted, delete the head of the linked list by assigning the head to the next node, set deleted to TRUE, and return deleted.

  4. Check if the value to be deleted is in the head node.

    1. If it is, update the head to the next node, effectively removing the head node. Set deleted to TRUE to indicate successful deletion, and return deleted.

    2. Otherwise, traverse the linked list using current until the end of the linked list. While traversing, check if the value of the current matches the value to be deleted.

      1. If the value matches, update the next pointer of the previous node to the next of current node. Also, disconnect the current node from the linked list by setting its next pointer to NULL, set deleted to TRUE and return deleted.

  5. After traversing the entire linked list, if the value is not found, return deleted, which remains FALSE. This indicates that the value is not found in the linked list.

Let’s look at the illustration below to better understand the solution:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.