0

Delete value from singly linked list

Problem:

Given a Linked List of Integers Delete all nodes that have value x.

Logic:

The basic thing we need to take into consideration is that given value can be present in a linked list more than once. So we will traverse to complete list while deleting a value. To keep a track if value is deleted from linked list or  if  value is not present in list, we will maintain a flag variable.

There are three spots from where you can delete the given node :

1) Node to delete is the first node :

Just assign current Head’s next as Head and delete the head ! 😀

It is possible that newly made head node also contains a same value(val that is to be deleted), eg. list [1,1,3] that is why we are checking head value repeatedly until its other that given val or head becomes null.

2) Node to delete is last node :

If given value is present in last node then we just need to make, next value of its previous node ‘null’.

3) Neither last nor first (Intermediate Node) :

Consider this linked list x->y->z and you want to delete y, then to delete y ,

x.next becomes z and y.next becomes null;

 

 

Below is implementation of this logic:

As all the nodes of linked list are traversed, time complexity of this operation is O(n).