Remove Linked List Elements solution and explanation
Google
TCS
9 more videos on this problem
Remove Linked List Elements - Leetcode 203NeetCode · 7:51 · 82K views
LeetCode 203. Remove Linked List Elements Solution Explained - JavaNick White · 4:35 · 39K views
Remove Linked List Elements (LeetCode 203) | Quick and Easy Explanation | Study AlgorithmsNikhil Lohia · 12:46 · 17K views
LEETCODE 203 (JAVASCRIPT) | REMOVE LINKED LIST ELEMENTSAndy Gala · 9:34 · 5K views
Remove Linked List Elements | LeetCode 203 | Coding Interview TutorialTerrible Whiteboard · 12:12 · 5K views
Remove Linked List Elements | Leet code 203 | Theory explained + Python codeSai Anish Malla · 3:44 · 3K views
Remove Linked List Elements | Day 20 | [ July LeetCoding Challenge ] [ Leetcode #203] [ 2020 ]Algorithms Made Easy · 4:01 · 1K views
LeetCode 203. Remove Linked List Elements Solution Explained - PythonHelmyCodeCamp · 7:47 · 773 views
Leetcode 203. Remove Linked List Elements - recursiveCoding Allies · 13:19 · 709 views
Remove Linked List Elements - LeetCode 203 - JavaLeetCode University · 16:40 · 664 views
The problem
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.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
dummy = ListNode(0)
dummy.next = head
current = dummy
while current and current.next:
if current.next.val == val:
current.next = current.next.next
else:
current = current.next
return dummy.nextclass ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode current = dummy;
while (current.next != null) {
if (current.next.val == val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return dummy.next;
}
}#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* current = dummy;
while (current->next != nullptr) {
if (current->next->val == val) {
ListNode* temp = current->next;
current->next = current->next->next;
delete temp;
} else {
current = current->next;
}
}
ListNode* newHead = dummy->next;
delete dummy;
return newHead;
}
};function ListNode(val, next) {
this.val = (val===undefined ? 0 : val);
this.next = (next===undefined ? null : next);
}
var removeElements = function(head, val) {
let dummy = new ListNode(0);
dummy.next = head;
let current = dummy;
while (current.next !== null) {
if (current.next.val === val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return dummy.next;
};#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode *dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
dummy->next = head;
struct ListNode *current = dummy;
while (current->next != NULL) {
if (current->next->val == val) {
struct ListNode *temp = current->next;
current->next = current->next->next;
free(temp);
} else {
current = current->next;
}
}
struct ListNode *newHead = dummy->next;
free(dummy);
return newHead;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode RemoveElements(ListNode head, int val) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode current = dummy;
while (current.next != null) {
if (current.next.val == val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return dummy.next;
}
}The dummy node acts as a safe starting pointer. The current pointer traverses the list, and if the next node's value equals val, it is removed by skipping it. Otherwise, the loop continues with the next node. At the end, the head of the modified list is returned, which starts after the dummy node.
Time Complexity: O(n) for iterating through the list.
Space Complexity: O(1) as only a few extra variables are used.
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.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
if not head:
return None
head.next = self.removeElements(head.next, val)
return head.next if head.val == val else headclass ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) return null;
head.next = removeElements(head.next, val);
return head.val == val ? head.next : head;
}
}#include <iostream>
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;
}
};function ListNode(val, next) {
this.val = (val===undefined ? 0 : val);
this.next = (next===undefined ? null : next);
}
var removeElements = function(head, val) {
if (head === null) return null;
head.next = removeElements(head.next, val);
return head.val === val ? head.next : head;
};#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* removeElements(struct ListNode* head, int val) {
if (head == NULL) return NULL;
head->next = removeElements(head->next, val);
return head->val == val ? head->next : head;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode RemoveElements(ListNode head, int val) {
if (head == null) return null;
head.next = RemoveElements(head.next, val);
return head.val == val ? head.next : head;
}
}In Python, the function recursively progresses through the entire list and processes each node as the recursion unwinds. On each return, a determination is made about the inclusion or exclusion of the head node by verifying its value against val.
Time Complexity: O(n), covering the entire length.
Space Complexity: O(n), dependent on recursion stack size.
Approach 3: Default Approach
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function removeElements(head: ListNode | null, val: number): ListNode | null {
const dummy: ListNode = new ListNode(0, head);
let cur: ListNode = dummy;
while (cur.next != null) {
if (cur.next.val === val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return dummy.next;
}func removeElements(head *ListNode, val int) *ListNode {
dummy := new(ListNode)
dummy.Next = head
p := dummy
for p.Next != nil {
if p.Next.Val == val {
p.Next = p.Next.Next
} else {
p = p.Next
}
}
return dummy.Next
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn remove_elements(head: Option<Box<ListNode>>, val: i32) -> Option<Box<ListNode>> {
let mut dummy = Box::new(ListNode { val: 0, next: head });
let mut cur = &mut dummy;
while let Some(mut node) = cur.next.take() {
if node.val == val {
cur.next = node.next.take();
} else {
cur.next = Some(node);
cur = cur.next.as_mut().unwrap();
}
}
dummy.next.take()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Iterative with Dummy Head | Time Complexity: O(n) for iterating through the list. |
| Approach 2: Recursive Method | Time Complexity: O(n), covering the entire length. |
| Default Approach | – |
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. |
Frequently asked questions
Is Remove Linked List Elements easy or hard?
Remove Linked List Elements is categorized as an Easy problem on LeetCode. It mainly tests understanding of linked list traversal and pointer updates, making it a common starter problem for practicing linked list manipulation.
Remove Linked List Elements Python/Java solution
Python and Java solutions typically implement the dummy head technique. Create a sentinel node pointing to the head, iterate through the list, and bypass nodes whose value matches the target. The same logic applies across C++, C#, and JavaScript implementations.
How to solve Remove Linked List Elements in O(n)?
Traverse the linked list while maintaining a previous pointer. If the current node's value equals the target value, update prev.next to skip that node. Using a dummy head before the real head simplifies edge cases and guarantees a single O(n) pass.
What is the best approach for Remove Linked List Elements?
The iterative approach using a dummy head node is the most reliable solution. It traverses the list once and removes nodes by updating pointers, achieving O(n) time and O(1) extra space. The dummy node avoids edge cases where the head itself needs to be removed.
Is Remove Linked List Elements asked at Google/Amazon/Meta?
Linked list deletion and pointer manipulation problems are common across major tech interviews including Amazon, Google, and Meta. Variants of this question frequently appear in early interview rounds to evaluate basic data structure fundamentals.
What data structure is used in Remove Linked List Elements?
The problem operates on a singly linked list. The key operations involve pointer traversal, node comparison, and pointer reassignment to remove nodes without breaking the list structure.
What is the time complexity of Remove Linked List Elements?
Both common solutions run in O(n) time because every node in the linked list is visited once. The iterative dummy-head method uses O(1) extra space, while the recursive approach uses O(n) stack space due to recursive calls.