Last Updated: 15 Mar, 2021
Remove All Nodes with Value K
Easy
Asked in companies
You are given a Singly Linked List of integers and an integer 'K'. Your task is to remove all such nodes from the linked list whose value is equal to 'K'.
A singly linked list is a linear data structure in which we can traverse only in one direction i.e., from Head to Tail. It consists of several nodes where each node contains some data and a reference to the next node.
A sample Linked List-
Input format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.
The first line of each test case contains space-separated integers denoting the values of nodes of the Linked List. The Linked List is terminated with -1. Hence, -1 is never a node value of the Linked List.
The second line of each test case contains a single integer 'K' which denotes the value of the nodes to be removed.
Output format:
For each test case, print the elements of the resultant Linked List after removing all nodes having the value 'K'.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^5
0 <= node.data <= 10^9 and node.data != -1
0 <= K <= 10^9
Where 'node.data' denotes the value of a Linked list node, and 'K' denotes the value of the nodes to be removed.
Time limit: 1 sec
Approaches
Approach: The idea is to use recursion to solve the problem. The working of the recursive function is explained below. The basic idea is pretty simple that if a node has value K, then we will remove this node from the Linked List, and our output will be the node returned by the recursive call for its next node. Otherwise, our output will be the current node itself.
Working of the recursive function:
- If the node ‘HEAD’ is a NULL node, then we will return the node ‘HEAD’. This serves as the base case.
- Let ‘TEMP’ be a node that stores the value returned by recursive call for the node ‘HEAD → NEXT'.
- Update ‘HEAD -> NEXT' as ‘TEMP’, as ‘TEMP’ is the head of the Linked List after removing all occurrences of the value ‘K’.
- If ‘HEAD → DATA' is equal to K, then we will return the node ‘HEAD → NEXT'. As we want the current node to be removed from the Linked List, so we are returning its next node as the head of the Linked List.
- Otherwise, we will return the node ‘HEAD’.
Approach: The idea is to convert the previous approach into an iterative approach. To do so, we will find the first node from the left whose value is not equal to ‘K’. This node will be the head node of our final Linked List. Now we will iterate through the right of this node and will insert all the nodes in the Linked List whose value is not equal to ‘K’.
Steps:
- Let ‘NEWHEAD’ be a node that stores the head node of the final Linked List. Initialize it as 'HEAD'.
- While ‘NEWHEAD’ is not a NULL node and 'NEWNODE->DATA' is equal to K, then
- Set ‘NEWHEAD’ to 'NEWNODE->NEXT'.
- If ‘NEWHEAD’ is a NULL node, then we will return NULL as all nodes of the original Linked List have value ‘K’, therefore the resultant Linked List is empty.
- Let tail be a node that points to the tail(last node) of the Linked List. Initialize it as ‘NEWHEAD’.
- Let 'CURRNODE' be an iterator to the Linked List. Initialize it as 'NEWNODE->NEXT'.
- While 'CURRNODE' is not a NULL node, then
- If ‘CURRNODE→DATA’ is not equal to K, then set ‘TAIL->NEXT’ as ‘CURRNODE’ and update ‘TAIL’ to ‘TAIL->NEXT’.
- Set 'CURRNODE' as ‘CURRNODE→NEXT’.
- Set ‘TAIL->NEXT’ as NULL, as it is the tail node, and therefore it should not have any next node.
- Return the node ‘NEWHEAD’.