This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 203. This is a Leet code problem named Remove Linked List Elements. We will solve it using python and it is the best space and time-optimized solution.
Question of Remove Linked List Elements
Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.
Let us formulate the problem statement to understand the deletion process. Given a ‘key’, delete all the occurrences of this key in the linked list.
Example
Example 1
Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]
Example 2
Input: head = [], val = 1
Output: []
Example 3
Input: head = [7,7,7,7], val = 7
Output: []
Constraints
The number of nodes in the list is in the range [0, 104].
1 <= Node.val <= 50
0 <= val <= 50
Approach to solve Remove Linked List Elements
To solve this problem we will simply traverse through the whole linked list once and compare each node value with the given value. When the value is equal to the given value then we change the next pointer of the previous node. The next pointer of the previous node is assigned to the next of the found node. So in this way we skip the desired node.
Here we use two more pointer heads they are:
temp_head : this head is used to traverse through the linked list.
prev_head : This head is used to store the previous head while we are traversing to the linked list.
Algorithm
This method performs the following steps for a given input array:
Check for base case i.e. if the head is none then return head.
Create two variables named temp_head and prev_head and assign head to both of them.
Repeat steps 4 to 11 till the head is not none.
Check if the value of the current temp_head is equal to the value or not. If yes then go to step 5 otherwise go to step 9 .
Check if the current element is the first element or not if yes then do step 6 otherwise 7.
update head with next of head and update prev_head to next of prev_head.
Assign next of prev_head to next of temp_head.
End inner if
Check if it first node, If yes then update prev_head to next of prev_head.
end inner and outer if.
update temp_head to next of temp_head.
End While.
Python Code to Remove Linked List Elements
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
#check base case
if(head==None):
return head
#assign head to temp head and prev_head
temp_head = head
prev_head = head
#traverse through the link list till end of list
while(temp_head):
#check if current value is equal to the value which we want to delete
if(temp_head.val == val ):
#check if it is first element or not
if(temp_head == prev_head):
#if first element then head and prev_head both will assign to next of current node
head = head.next
prev_head = prev_head.next
else:
#Unlink the node from linked list
prev_head.next = temp_head.next
else:
#if it is not first node then prev_head to prev_head.next
if(temp_head!=prev_head):
prev_head = prev_head.next
#change temp_head to temp_head.next
temp_head = temp_head.next
#return head
return head
Complexity Analysis
Time Complexity: O(n)
Where n is number of nodes.
Space Complexity: O(1)
So here is the end of the post. If you find any issues or any questions then write a comment. Share with your friends.
This is really interesting, You’re an overly skilled blogger.
I’ve joined your rss feed and stay up for in the hunt for more
of your fantastic post. Additionally, I have shared your website in my social networks
This is really interesting, You’re an overly skilled blogger.
I’ve joined your rss feed and stay up for in the hunt for more
of your fantastic post. Additionally, I have shared your website in my social networks
Thanks Lonny