Log inSign up
easyLeetCodeNot Started

Remove Linked List Elements

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

Given the head of a linked list and an integer val, remove all the nodes of the linked list that have 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]
Explanation: Nodes containing value 6 at indices 2 and 6 are excised from the list.

Example 2:

Input: head = [], val = 1
Output: []
Explanation: Empty list produces an empty list.

Example 3:

Input: head = [7,7,7,7], val = 7
Output: []
Explanation: Every node matches target val = 7, so all are removed.

Constraints:

  • The number of nodes in the list is in the range [0, 10^4].
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

1. Array Extraction and Rebuild

Intuition

1. Iterate through the input list, appending any node.val != val into an array/list. 2. Iterate through the collected array and allocate new ListNode instances linked sequentially. 3. Return the head of the new list.

When to apply: Quick conceptual prototype when linked list pointer manipulations are prohibited or tricky.

Algorithm

  1. Traverse linked list and append values != val to a dynamic array nums.
  2. If nums is empty, return null.
  3. Create a new list from elements in nums and return its head.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4struct ListNode {
5 int val;
6 ListNode *next;
7 ListNode() : val(0), next(nullptr) {}
8 ListNode(int x) : val(x), next(nullptr) {}
9 ListNode(int x, ListNode *next) : val(x), next(next) {}
10};
11
12class Solution {
13public:
14 ListNode* removeElements(ListNode* head, int val) {
15 std::vector<int> kept;
16 ListNode* curr = head;
17 while (curr != nullptr) {
18 if (curr->val != val) {
19 kept.push_back(curr->val);
20 }
21 curr = curr->next;
22 }
23 if (kept.empty()) return nullptr;
24
25 ListNode* newHead = new ListNode(kept[0]);
26 ListNode* tail = newHead;
27 for (size_t i = 1; i < kept.size(); ++i) {
28 tail->next = new ListNode(kept[i]);
29 tail = tail->next;
30 }
31 return newHead;
32 }
33};
34
35int main() {
36 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(6, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6)))))));
37 Solution sol;
38 ListNode* res = sol.removeElements(head, 6);
39 while (res != nullptr) {
40 std::cout << res->val << " ";
41 res = res->next;
42 }
43 std::cout << std::endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(N) — We perform one pass to collect values (N steps) and a second pass to construct N new nodes.
  • Space complexity: O(N) — O(N) extra memory to hold the filtered values in an array and allocate duplicate nodes.

2. Recursive Post-Order Filtering

Intuition

1. Base case: If head == null, return null. 2. Recursive step: head.next = removeElements(head.next, val). 3. If head.val == val, return head.next (skipping current node); otherwise return head.

When to apply: Functional or recursive programming paradigms.

Algorithm

  1. If head == null, return null.
  2. Set head.next = removeElements(head.next, val).
  3. Return head.val == val ? head.next : head.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11class Solution {
12public:
13 ListNode* removeElements(ListNode* head, int val) {
14 if (!head) return nullptr;
15 head->next = removeElements(head->next, val);
16 return head->val == val ? head->next : head;
17 }
18};
19
20int main() {
21 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(6, new ListNode(3, new ListNode(6)))));
22 Solution sol;
23 ListNode* res = sol.removeElements(head, 6);
24 while (res != nullptr) {
25 std::cout << res->val << " ";
26 res = res->next;
27 }
28 std::cout << std::endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(N) — Visits each node exactly once in post-order order.
  • Space complexity: O(N) recursion stack — Requires O(N) call stack frames for a list of length N, which may cause stack overflow for N = 104 in shallow recursion limit environments.

3. Iterative Sentinel (Dummy Head) Pointer Bypass

Intuition

1. Create a sentinel node dummy such that dummy.next = head. 2. Set curr = dummy. 3. While curr.next != null: a. If curr.next.val == val, bypass: curr.next = curr.next.next (do NOT advance curr). b. Else, advance curr = curr.next. 4. Return dummy.next.

When to apply: The gold standard industry approach for in-place deletion with O(1) extra space and single-pass O(N) time.

Algorithm

  1. Allocate sentinel dummy with dummy.next = head.
  2. Set curr = dummy.
  3. While curr.next != null:
  4. - If curr.next.val == val: curr.next = curr.next.next
  5. - Else: curr = curr.next
  6. Return dummy.next.

Linked List Interactive Dry Run

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
curr
Visual state
Values and pointers at this exact step
linked list
This linked list trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Why this step matters

curr.next is node 1 (val 1 != 6).

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11class Solution {
12public:
13 ListNode* removeElements(ListNode* head, int val) {
14 ListNode dummy(0, head);
15 ListNode* curr = &dummy;
16
17 while (curr->next != nullptr) {
18 if (curr->next->val == val) {
19 ListNode* temp = curr->next;
20 curr->next = curr->next->next;
21 delete temp; // Free memory in C++
22 } else {
23 curr = curr->next;
24 }
25 }
26 return dummy.next;
27 }
28};
29
30int main() {
31 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(6, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6)))))));
32 Solution sol;
33 ListNode* res = sol.removeElements(head, 6);
34 while (res != nullptr) {
35 std::cout << res->val << " ";
36 res = res->next;
37 }
38 std::cout << std::endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N) — Every node is inspected at most once in a single pass of length N.
  • Space complexity: O(1) auxiliary — Only requires one dummy pointer node and one iterator pointer: strict O(1) space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Array Extraction and RebuildO(N)O(N)Extract all values not equal to val into an auxiliary dynamic array, then reconstruct a brand new linked list.High time complexity
2.Recursive Post-Order FilteringO(N)O(N) recursion stackRecursively process the tail of the list first, and link the current node to the filtered tail if its value is not val.—
3.Iterative Sentinel (Dummy Head) Pointer BypassOptimalO(N)O(1) auxiliaryUse a dummy head sentinel node preceding head and iterate through the list with a single pointer curr, updating curr.next = curr.next.next whenever target val is found.—

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Advancing curr = curr.next even after deleting a node: if multiple consecutive target nodes exist (e.g. [6, 6]), skipping curr.next without advancing pointer is necessary to delete the second one.

Pitfall 2:

Forgetting to handle head node deletion: not using a dummy node requires special-case while (head != null && head.val == val) head = head.next; loops.

Pitfall 3:

Memory leaks in C++: failing to delete the unlinked node before re-assigning pointers.

Back to DSA Sheet