How to Answer: Remove elements from linked list that are equal to target.
Advice and answer examples written specifically for a Python Beginner Level Linked Lists job interview.
3. Remove elements from linked list that are equal to target.
This interview question shows the developer's ability to use Python 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 of 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
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeElements(head: ListNode, target: int) -> ListNode:
if not head:
return None
head.next = removeElements(head.next, target)
return head.next if head.val == target else headn = 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 the next of curr to the 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.
class ListNode:
def __init__(self, val = 0, next = None):
self.val = val
self.next = next
def removeElements(head: ListNode, target: int) -> ListNode:
if head is None: return head
curr = head
while curr and curr.next:
if curr.next.val == target:
curr.next = curr.next.next
else:
curr = curr.next
return head if head.val != target else head.nextn = length linked list
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on May 21st, 2021