Remove Linked List Elements - Solution & Explanation
Problem Statement
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:
- The number of nodes in the list is in the range
[0, 104]. 1 <= Node.val <= 500 <= val <= 50
Approach Overview
Problem 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.
Approach 1: Approach 1: Iterative with Dummy Head
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.
Complexity
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.
Approach 2: Approach 2: Recursive Method
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.
Complexity
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 3: Default Approach
Try this approach in the editor →Complexity Comparison
| 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. |
| Default Approach | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Remove Linked List Elements - Leetcode 203 • NeetCode • 82,225 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Remove Linked List Elements easy or hard?
Remove Linked List Elements Python/Java solution
How to solve Remove Linked List Elements in O(n)?
What is the best approach for Remove Linked List Elements?
Is Remove Linked List Elements asked at Google/Amazon/Meta?
What data structure is used in Remove Linked List Elements?
What is the time complexity of Remove Linked List Elements?
Ready to solve this problem?
Practice Remove Linked List Elements with our built-in code editor and test cases.
Practice on FleetCode