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: []
Constraints:
[0, 104].1 <= Node.val <= 500 <= val <= 50In #203 Remove Linked List Elements, the goal is to remove all nodes from a singly linked list that contain a specific value. A common challenge is handling cases where the node to delete is the head itself. To simplify this, many solutions introduce a dummy node that points to the head. By iterating through the list and checking current.next, you can safely bypass nodes that match the target value without losing references. This approach ensures clean pointer manipulation and avoids repeated head updates.
Another elegant technique uses recursion. The recursive call processes the remainder of the list first, then decides whether to keep or skip the current node based on its value. This creates a concise solution where each call returns the corrected sublist.
The iterative method runs in O(n) time with O(1) extra space, while the recursive approach also takes O(n) time but uses additional stack space due to recursion.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative with Dummy Node | O(n) | O(1) |
| Recursive Linked List Traversal | O(n) | O(n) |
NeetCode
This approach involves using a dummy node to handle the removal of nodes, including edge cases where the head node itself needs to be removed. We use a pointer to traverse the list, comparing each node's value with the target val. If the node needs to be removed, we adjust the pointers to skip the node. If not, we just move to the next node.
Time Complexity: O(n), where n is the number of nodes in the linked list, as we must traverse all nodes.
Space Complexity: O(1) because we are using constant extra space.
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int val = 0, ListNode next = null) {
5 this.val = val;
6 this.next = next;
7 }
8}
9
10public class Solution {
11 public ListNode RemoveElements(ListNode head, int val) {
12 ListNode dummy = new ListNode(0);
13 dummy.next = head;
14 ListNode current = dummy;
while (current.next != null) {
if (current.next.val == val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return dummy.next;
}
}We initialize with a dummy node to manage the removal process smoothly without special conditions for the head. The current node progresses through the list. Nodes are removed by modifying the next pointers. At the conclusion, after addressing all nodes, the modified list is returned.
This approach employs a recursive strategy to tackle the problem. The idea is to attempt removing elements starting from the rest of the list and linking the current node to the result of this removal. If the head node itself needs removal, simply return the result of removing nodes from the rest of the list by moving the reference forward.
Time Complexity: O(n), as each node is processed exactly once.
Space Complexity: O(n), due to the recursion stack for n nodes in the longest path.
1
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if (!head) return nullptr;
head->next = removeElements(head->next, val);
return head->val == val ? head->next : head;
}
};Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, linked list manipulation problems like this are common in technical interviews at FAANG and other top companies. They test understanding of pointer operations, edge case handling, and algorithmic thinking.
Yes, recursion is a clean alternative approach. Each recursive call processes the next node first and then decides whether to keep or remove the current node, effectively rebuilding the list during the return phase.
A singly linked list is the core data structure used in this problem. Understanding pointer manipulation and node traversal is essential for efficiently removing elements without breaking the list.
The optimal approach uses an iterative traversal with a dummy node pointing to the head. This helps handle edge cases where the head itself must be removed and allows safe pointer updates while skipping nodes with the target value.
The recursive function iterates through the linked list. For each node, it first attempts to remove the nodes with the appropriate value from the rest of the list. If it finds the current node should be removed, it skips and returns the processed remainder.