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 <= 50Problem Overview: You receive the head of a singly linked list and an integer val. Remove every node whose value equals val and return the updated head. The challenge is handling deletions cleanly, especially when the head itself must be removed.
Approach 1: Iterative with Dummy Head (O(n) time, O(1) space)
The cleanest solution uses a dummy head node placed before the actual list head. This extra node removes the special case where the first node needs to be deleted. Start with two pointers: prev and curr. Iterate through the list; if curr.val == val, skip the node by setting prev.next = curr.next. Otherwise move both pointers forward. Every node is visited exactly once, giving O(n) time complexity and constant O(1) extra space.
This approach is widely used for linked list deletion problems because pointer updates stay simple and predictable. The dummy node ensures the returned head is always dummy.next, even if the original head gets removed.
Approach 2: Recursive Method (O(n) time, O(n) space)
The recursive approach processes the list from the end back to the front. For each node, recursively clean the remainder of the list using head.next = removeElements(head.next, val). Once the rest of the list is fixed, check the current node: if head.val == val, return head.next; otherwise return the current node.
Each node participates in exactly one recursive call, so the total work remains O(n). The trade‑off is stack usage: recursion requires O(n) auxiliary space due to the call stack. This method is concise and elegant but less memory‑efficient than iteration. It’s useful when practicing recursion patterns on linked structures.
Recommended for interviews: The iterative dummy‑head approach is the expected solution. It demonstrates strong pointer manipulation skills and constant space optimization. Mentioning recursion shows conceptual understanding of linked list structure, but the iterative version is typically preferred in production and interviews because it avoids stack overhead.
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.
We create a dummy node that points to the head of the list to handle edge cases seamlessly. The current pointer is initialized to the dummy node. We traverse the linked list, and if the next node's value equals the target val, we adjust the pointers to remove it. Otherwise, we move the current pointer forward. Finally, we free the dummy node and return the new head of the list.
C++
Java
Python
C#
JavaScript
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.
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.
This solution employs a recursive function that processes the rest of the list first and then makes a decision about the current node. If the current node’s value matches val, the function returns the next node as the new head; otherwise, it returns itself linked to the result of the processed rest.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Approach 1: Iterative with Dummy Head | Time Complexity: O(n), where n is the number of nodes in the linked list, as we must traverse all nodes. |
| Approach 2: Recursive Method | Time Complexity: O(n), as each node is processed exactly once. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative with Dummy Head | O(n) | O(1) | Best general solution. Handles head deletions cleanly and avoids recursion stack. |
| Recursive Method | O(n) | O(n) | Useful for practicing recursion on linked lists or when code brevity is preferred. |
Remove Linked List Elements - Leetcode 203 • NeetCode • 71,212 views views
Watch 9 more video solutions →Practice Remove Linked List Elements with our built-in code editor and test cases.
Practice on FleetCode