Watch 10 video solutions for Remove Linked List Elements, a easy level problem involving Linked List, Recursion. This walkthrough by NeetCode has 71,212 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |