How to Answer: Remove elements from the linked list that are equal to the target.
Advice and answer examples written specifically for a Java Beginner Level Linked Lists job interview.
3. Remove elements from the linked list that are equal to the target.
This question focuses on Java recursion and iteration.
You are given the head of a linked list. You are also given a target value. Your task is to remove all the nodes from the linked list whose value is equal to the target.
/*Example*/
Given: linked list => 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 target = 6
Expected output: 1 -> 2 -> 3 -> 4 -> 5Solution:
Approach I (recursive):
In the recursive approach, we will check the value of the current node in the function call. If the value of the current node i.e. head in the function call is equal to target, we return next of head instead of returning head. Before doing that, we recursively check and remove the next head. For example: for list 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6, the calls are:
(rm denotes the function removeElements)
|rm(1)
| |rm(2)|
| | |rm(6)|
| | | |rm(3)|
| | | | |rm(4)|
| | | | | |rm(5)|
| | | | | | |rm(6)|
| | | | | | | |rm(null)
| | | | | | | | return null
| | | | | | | |head.next = null
| | | | | | | |head.val == 6; // 6 == 6 => true
| | | | | | | |return head.next(null)
| | | | | | |head.next = null
| | | | | | |head.val == 6; // 5 == 6 => false
| | | | | | |return head(5)
| | | | | |head.next = 5
| | | | | |head.val == 6 // 4 == 6 => false
| | | | | |return head(4)
| | | | |head.next = 4
| | | | |head.val == 6 // 3 == 6 => false
| | | | |return head(3)
| | | |head.next = 3
| | | |head.val == 6 // 6 == 6 => true
| | | |return head.next(3)
| | |head.next = 3
| | |head.val == 6 // 2 == 6 => false
| | |return head(2)
| |head.next = 2
| |head.val == 6 // 1 == 6 => false
| |return head(1)
The resulting list is the return of all the function calls i.e. 1 -> 2 -> 3 -> 4 -> 5
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) return null;
head.next = removeElements(head.next, val);
return head.val == val ? head.next : head;
}
}n = length linked list
Time complexity- O(n)
Space complexity- O(n)
Approach II (iterative):
In the iterative approach, we loop over all the nodes in the list. From the current node curr, if it has a next node (curr.next) and its value is equal to the target, we will remove the next node. To remove we will set next of curr to next of curr.next.
After the loop, all the nodes with value target will be removed except at the head. So after the loop, we will check for the head node too.
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) return null;
ListNode curr = head;
while(curr != null && curr.next != null) {
if (curr.next.val == val) {
curr.next = curr.next.next;
} else {
curr = curr.next;
}
}
// the first node
if (head.val == val) head = head.next;
return head;
}
}n = length linked list
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on May 21st, 2021