Java Solution for removing elements for linked list
Introduction
In this article, we will solve the leetcode 203 where we will remove the elements from the linked list. In this problem, we will discuss the solution through visual representation, covering some edge cases, and at the end discuss time and space complexity.
Problem
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.
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: []
Solution
Memory Dump
- In the linked list removal problem, removal means fixing the linking of the nodes based on requirements.
- So if we want to remove certain nodes, we will need to fix the linking to the target from the previous node by pointing it to the next node of the target node.
- In the below diagram, we can see, that to remove the nodes with the value of 1, we fix the link of the node previous to it by pointing it to the next node (i.e. 2) of the target node (i.e. 1).
- Due to the above operation, our linked list does not include a node with value 1 since there is no way to reach it and it will be removed by a process called garbage collection.
Intuition
- Now if the removal of the nodes in the linked list is all about fixing the link of the nodes, then we can use this knowledge, do a single pass to our linked list, and fix the nodes linking whenever we see the target value that we need to remove.
- As we saw in the memory dump info, to remove a target node we need the info of the previous node and the next node of the target node.
- This makes an interesting edge case when we need to remove the target node which happens to be the head node (i.e. first node ) of the linked list. Since we don’t have a previous node for the head node, generally for any of our logic of single pass we miss this element from the operation.
- So either we have to handle it at the last or introduce a dummy pointer logic. where we create a dummy pointer that points to the head node and we assign the previous node to this dummy pointer.
Without Dummy Pointer:
- In this solution, we are first storing a reference to head to another node called headNode which we will use to return the result.
- We will use two pointers prev and head, and we will move these pointer to fix the linking of the nodes.
ListNode headNode = head;
if(headNode==null)
return head;
ListNode prev = head;
- Now we are ready to do the single pass to the linked list where we will relink the nodes which are previous to the target nodes.
- In the below logic, we are doing a single pass, at first, we check if the current node value is the target value, if yes then we should relink the previous node next to the current node (i.e. head. next ).
while(head!=null){
if(head.val == val){
prev.next = head.next;
}else{
prev = head;
}
head = head.next;
}
- Below is the visual representation of the logic of single pass and relinking of the nodes.
… continue further with the same logic.
- In this logic, we have to handle the first/head node separately as a single check at last since our current logic would skip the first node from removal if it’s the target node.
- So to handle this, we can have a check at the last if the head matches with the target, we can move the pointer to the next node since we have fixed the linking from the next node already.
if(headNode.val == val){
return headNode.next;
}
- That’s the entire logic for the removal of the nodes in the linked list. Below is the entire logic.
/**
* Definition for singly-linked list.
* 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) {
ListNode headNode = head;
if(headNode==null)
return head;
ListNode prev = head;
while(head!=null){
if(head.val == val){
prev.next = head.next;
}else{
prev = head;
}
head = head.next;
}
if(headNode.val == val){
return headNode.next;
}
return headNode;
}
}
- Our solution gets accepted and its pretty efficient ( beats 91%)
With Dummy Pointer
- With a dummy pointer, we solve the issue of skipping the first node if it’s the target node.
- This skipping issue happened because at the start previous node and head were pointing to the same node. So it didn’t get the opportunity to relink the previous node if the head was the target node itself.
- Now with a dummy pointer, we introduce a dummy pointer and point that to the head. Our previous node would be equal to a dummy pointer.
- The most important point here is that the previous node is not the same head as we saw in the earlier solution.
ListNode dummy = new ListNode(0, head);
- Now our previous node will get the opportunity to relink the next node if the head is the target itself.
- Now we just have to make sure that we don’t return the dummy node, we should return the dummy_node.next since that is where our result node starts.
return dummy.next;
- Below is the entire logic for the dummy pointer solution which is the same as without a dummy pointer except no need to handle the edge case.
/**
* Definition for singly-linked list.
* 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) {
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;
while(head!=null){
if(head.val == val) {
prev.next = head.next;
}else{
prev = head;
}
head = head.next;
}
return dummy.next;
}
}
- Our solution is accepted and pretty efficient.
Complexity
- Both the solution has a time complexity of O(N) since we are iterating over each node once i.e. single pass.
- Space complexity is O(1) i.e. constant since we are not using any additional space.
Conclusion
- In this article, we solved the removal of elements from the linked list. We discussed about edge case of the handling head node. Additionally, we discussed the time complexity and space complexity.
Crack DSA interview with
- Java DSA Made Visual → Learn from Engaging Animations
(BestSeller 4.7/5.0, 37k students) - Mastering Leetcode In Java — Top 100 Most Asked Problems
( Highest Rated (4.7/5.0))
Subscribe to Java Newsletter to keep up with all the updates in Java/Spring world.