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:
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:
Initialize a boolean variable,
deleted
, with FALSE to track whether the deletion is successful.Initialize a
current
pointer to the head of the linked list and aprevious
pointer to NULL.If
current
is pointing to the value to be deleted, delete thehead
of the linked list by assigning thehead
to the next node, setdeleted
to TRUE, and returndeleted
.Check if the value to be deleted is in the
head
node.If it is, update the
head
to the next node, effectively removing thehead
node. Setdeleted
to TRUE to indicate successful deletion, and returndeleted
.Otherwise, traverse the linked list using
current
until the end of the linked list. While traversing, check if the value of thecurrent
matches thevalue
to be deleted.If the value matches, update the
next
pointer of theprevious
node to thenext
ofcurrent
node. Also, disconnect thecurrent
node from the linked list by setting itsnext
pointer to NULL, setdeleted
to TRUE and returndeleted
.
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.