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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
public Node RemoveElements(Node head, int val) { if (head == null) { Console.WriteLine("Linked list is empty"); return head; } while (head != null && head.val == val) { head = head.next; } if (head == null) { return head; } Node tempNode = head; bool flag = false; while (tempNode.next != null) { while (tempNode.next.val == val && tempNode.next.next != null) { tempNode.next = tempNode.next.next; flag = true; } if (tempNode.next.val == val && tempNode.next.next == null) { tempNode.next = null; flag = true; return head; } tempNode = tempNode.next; } if (tempNode.next == null && flag == false) { Console.WriteLine("Value does not exist in linked list"); } return head; } |
As all the nodes of linked list are traversed, time complexity of this operation is O(n).