89. Remove Linked List Elements
🔗 LeetCode Problem: 203. Remove Linked List Elements
📊 Difficulty: Easy
🏷️ Topics: Linked List, Recursion
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]
Visual:
Before: 1 → 2 → 6 → 3 → 4 → 5 → 6 → null
After: 1 → 2 → 3 → 4 → 5 → null
(removed both 6's)
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, 10^4].
- 1 <= Node.val <= 50
- 0 <= val <= 50
🌟 ELI5: The Simple Idea!
Think of removing people from a queue:
Queue: [Alice, Bob, Charlie, Bob, Dave, Bob]
Task: Remove all "Bob"s
Method 1: Without marking the front
- Need special handling for first person
- If first is Bob, move everyone forward
- Then check rest one by one
Method 2: Add a marker at the front
- Put a "START" marker before Alice
- Now you can check everyone uniformly
- "Does next person = Bob? Skip them!"
- No special case for first person!
Result: [Alice, Charlie, Dave]
The Dummy Node Trick:
Without dummy:
head = [6, 1, 2, 6], remove 6
First is 6! Special case needed!
With dummy:
dummy → 6 → 1 → 2 → 6
Now can check all uniformly:
"Is next node 6? Skip it!"
🎨 Visual Understanding
The Removal Process
Initial: head = [1, 2, 6, 3, 4, 5, 6], val = 6
Step 1: Add dummy node
dummy → 1 → 2 → 6 → 3 → 4 → 5 → 6 → null
↑
current
Step 2: Check current.next
current at dummy, next is 1
1 == 6? No, keep it
Move current forward
dummy → 1 → 2 → 6 → 3 → 4 → 5 → 6 → null
↑
current
Step 3: Check current.next
current at 1, next is 2
2 == 6? No, keep it
Move current forward
dummy → 1 → 2 → 6 → 3 → 4 → 5 → 6 → null
↑
current
Step 4: Check current.next
current at 2, next is 6
6 == 6? YES! Skip it!
current.next = current.next.next
dummy → 1 → 2 → 3 → 4 → 5 → 6 → null
↑ (skipped 6)
current
DON'T move current (need to check new next)
Step 5: Check current.next (again)
current still at 2, next is now 3
3 == 6? No, keep it
Move current forward
dummy → 1 → 2 → 3 → 4 → 5 → 6 → null
↑
current
... continue until end ...
Step N: Final result
current.next = null, done!
dummy → 1 → 2 → 3 → 4 → 5 → null
Return: dummy.next (skip dummy)
Result: [1, 2, 3, 4, 5]
🎯 Approach 1: Dummy Node (Iterative) ⭐
The Recommended Solution
Why Dummy Node?
Problem: Head might need to be removed!
Without dummy:
[6, 6, 1, 2], val = 6
Need to handle: "while head == 6, head = head.next"
Then handle rest differently
Complex!
With dummy:
dummy → 6 → 6 → 1 → 2
Uniform logic: "if next == 6, skip it"
Simple!
Implementation
/**
* Iterative with dummy node
* Time: O(n), Space: O(1)
*/
public ListNode removeElements(ListNode head, int val) {
// Create dummy node to handle head removal
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode current = dummy;
// Traverse and remove matching nodes
while (current.next != null) {
if (current.next.val == val) {
// Skip the next node
current.next = current.next.next;
// DON'T move current - check new next node
} else {
// Keep the next node, move forward
current = current.next;
}
}
return dummy.next; // Return actual head (skip dummy)
}
⏰ Time: O(n) - Visit each node once
💾 Space: O(1) - Only dummy and current pointer
🔍 Super Detailed Dry Run
Example: head = [1, 2, 6, 3, 4, 5, 6], val = 6
Goal: Remove all 6's → [1, 2, 3, 4, 5]
Initial state:
head → 1 → 2 → 6 → 3 → 4 → 5 → 6 → null
dummy = new node(0)
dummy.next = head
dummy → 1 → 2 → 6 → 3 → 4 → 5 → 6 → null
↑
current
═══════════════════════════════════════════════════════════════
Iteration 1: Check node 1
═══════════════════════════════════════════════════════════════
State:
current = dummy
current.next = node 1
Condition: current.next != null (1) ✓
Check: current.next.val == val?
1 == 6? No
Action: Keep node, move forward
current = current.next
State after:
dummy → 1 → 2 → 6 → 3 → 4 → 5 → 6 → null
↑
current
═══════════════════════════════════════════════════════════════
Iteration 2: Check node 2
═══════════════════════════════════════════════════════════════
State:
current = node 1
current.next = node 2
Condition: current.next != null (2) ✓
Check: current.next.val == val?
2 == 6? No
Action: Keep node, move forward
current = current.next
State after:
dummy → 1 → 2 → 6 → 3 → 4 → 5 → 6 → null
↑
current
═══════════════════════════════════════════════════════════════
Iteration 3: Check node 6 (FIRST MATCH!)
═══════════════════════════════════════════════════════════════
State:
current = node 2
current.next = node 6
Condition: current.next != null (6) ✓
Check: current.next.val == val?
6 == 6? YES!
Action: Skip node
current.next = current.next.next
Before:
dummy → 1 → 2 → 6 → 3 → 4 → 5 → 6 → null
↑ ↑
current (skip this)
After:
dummy → 1 → 2 → 3 → 4 → 5 → 6 → null
↑ ↑
current (now points here)
DON'T move current! Need to check new next!
State after:
dummy → 1 → 2 → 3 → 4 → 5 → 6 → null
↑
current (stays here)
═══════════════════════════════════════════════════════════════
Iteration 4: Check node 3
═══════════════════════════════════════════════════════════════
State:
current = node 2 (same as before!)
current.next = node 3 (new next after removal)
Condition: current.next != null (3) ✓
Check: current.next.val == val?
3 == 6? No
Action: Keep node, move forward
current = current.next
State after:
dummy → 1 → 2 → 3 → 4 → 5 → 6 → null
↑
current
═══════════════════════════════════════════════════════════════
Iteration 5: Check node 4
═══════════════════════════════════════════════════════════════
State:
current = node 3
current.next = node 4
Condition: current.next != null (4) ✓
Check: current.next.val == val?
4 == 6? No
Action: Keep node, move forward
current = current.next
State after:
dummy → 1 → 2 → 3 → 4 → 5 → 6 → null
↑
current
═══════════════════════════════════════════════════════════════
Iteration 6: Check node 5
═══════════════════════════════════════════════════════════════
State:
current = node 4
current.next = node 5
Condition: current.next != null (5) ✓
Check: current.next.val == val?
5 == 6? No
Action: Keep node, move forward
current = current.next
State after:
dummy → 1 → 2 → 3 → 4 → 5 → 6 → null
↑
current
═══════════════════════════════════════════════════════════════
Iteration 7: Check node 6 (SECOND MATCH!)
═══════════════════════════════════════════════════════════════
State:
current = node 5
current.next = node 6
Condition: current.next != null (6) ✓
Check: current.next.val == val?
6 == 6? YES!
Action: Skip node
current.next = current.next.next
Before:
dummy → 1 → 2 → 3 → 4 → 5 → 6 → null
↑ ↑
current (skip this)
After:
dummy → 1 → 2 → 3 → 4 → 5 → null
↑
current
State after:
dummy → 1 → 2 → 3 → 4 → 5 → null
↑
current
═══════════════════════════════════════════════════════════════
Iteration 8: Check end
═══════════════════════════════════════════════════════════════
State:
current = node 5
current.next = null
Condition: current.next != null (null) ✗
Exit loop!
═══════════════════════════════════════════════════════════════
Return Result
═══════════════════════════════════════════════════════════════
Return: dummy.next
Final list:
1 → 2 → 3 → 4 → 5 → null ✓
Result: [1, 2, 3, 4, 5]
🎯 Approach 2: Without Dummy Node
Direct Manipulation (More Complex)
/**
* Without dummy node
* Time: O(n), Space: O(1)
* More complex due to head handling
*/
public ListNode removeElements(ListNode head, int val) {
// Remove from head while needed
while (head != null && head.val == val) {
head = head.next;
}
// If list became empty
if (head == null) {
return null;
}
// Remove from rest of list
ListNode current = head;
while (current.next != null) {
if (current.next.val == val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}
Why This is More Complex:
Extra logic needed:
1. Special loop for head removal
2. Check if list becomes empty
3. Different handling for head vs rest
Dummy node eliminates all this!
🎯 Approach 3: Recursive ⭐
Elegant Recursive Solution
Core Logic:
Recursively remove from rest of list
Then decide about current node
Base case: null → return null
Recursive case:
1. Process rest of list
2. If current should be removed, skip it
3. Otherwise, keep it
Implementation
/**
* Recursive approach
* Time: O(n), Space: O(n) - recursion stack
*/
public ListNode removeElements(ListNode head, int val) {
// Base case
if (head == null) {
return null;
}
// Recursively remove from rest
head.next = removeElements(head.next, val);
// Decide about current node
return (head.val == val) ? head.next : head;
}
⏰ Time: O(n) - Visit each node once
💾 Space: O(n) - Recursion call stack
🔍 Recursive Dry Run
Example: head = [1, 6, 2], val = 6
Goal: Remove 6 → [1, 2]
═══════════════════════════════════════════════════════════════
Call Stack Building
═══════════════════════════════════════════════════════════════
removeElements([1, 6, 2], 6)
head = 1, val = 6
head.next = removeElements([6, 2], 6)
↓
removeElements([6, 2], 6)
head = 6, val = 6
head.next = removeElements([2], 6)
↓
removeElements([2], 6)
head = 2, val = 6
head.next = removeElements(null, 6)
↓
removeElements(null, 6)
head = null
BASE CASE: return null
═══════════════════════════════════════════════════════════════
Unwinding Stack
═══════════════════════════════════════════════════════════════
Back to: removeElements([2], 6)
head.next = null
head.val (2) == val (6)? No
Return: head (2)
2 → null
Back to: removeElements([6, 2], 6)
head.next = 2 → null
head.val (6) == val (6)? YES!
Return: head.next (skip 6)
Return: 2 → null
Back to: removeElements([1, 6, 2], 6)
head.next = 2 → null
head.val (1) == val (6)? No
Return: head
1 → 2 → null
═══════════════════════════════════════════════════════════════
Result
═══════════════════════════════════════════════════════════════
Final list: 1 → 2 → null ✓
Visual Call Stack:
removeElements([1,6,2], 6) → Return 1→2
↓
removeElements([6,2], 6) → Return 2 (skip 6)
↓
removeElements([2], 6) → Return 2
↓
removeElements(null, 6) → Return null
Building back up:
[2]: 2.next = null, 2 != 6 → keep 2
[6,2]: 6.next = 2, 6 == 6 → skip, return 2
[1,6,2]: 1.next = 2, 1 != 6 → keep 1→2
🎯 Comparison of Approaches
Approach Time Space Code Recommended
═══════════════════════════════════════════════════════════════
Dummy Node O(n) O(1) Clean ⭐⭐⭐⭐⭐
Without Dummy O(n) O(1) Complex ⭐⭐
Recursive O(n) O(n) Elegant ⭐⭐⭐⭐
Recommended: Dummy Node
✓ Simplest code
✓ Uniform handling
✓ O(1) space
✓ Most common in interviews
Recursive:
✓ Very elegant
✓ Shows recursion skill
✗ Uses stack space
✓ Good alternative answer
⚠️ Common Mistakes
Mistake 1: Moving current when removing
// ❌ WRONG - Skips next node check!
if (current.next.val == val) {
current.next = current.next.next;
current = current.next; // DON'T MOVE!
}
// ✓ CORRECT - Stay to check new next
if (current.next.val == val) {
current.next = current.next.next;
// Don't move! New next might also need removal
}
Mistake 2: Checking current instead of current.next
// ❌ WRONG - Can't remove current itself!
if (current.val == val) {
// How to remove current? Lost reference!
}
// ✓ CORRECT - Check next node
if (current.next.val == val) {
current.next = current.next.next; // Can remove!
}
Mistake 3: Not using dummy for head removal
// ❌ WRONG - Head removal is messy
if (head.val == val) {
// Special case!
}
// Different logic for rest...
// ✓ CORRECT - Dummy handles all
ListNode dummy = new ListNode(0);
dummy.next = head;
// Uniform logic for all nodes!
Mistake 4: Returning dummy instead of dummy.next
// ❌ WRONG - Includes dummy in result!
return dummy;
// ✓ CORRECT - Skip dummy
return dummy.next;
Mistake 5: Not handling all-match case
// Example: [7, 7, 7], val = 7
// Result should be empty list (null)
// ✓ Code handles it naturally!
// After all removals, dummy.next = null
return dummy.next; // Returns null ✓
🎯 Pattern Recognition
Problem Type: Remove Nodes by Condition
Core Pattern: Dummy Node + Filter
When to Apply:
✓ Remove nodes matching value
✓ Remove nodes matching condition
✓ Filter linked list
✓ Head might be removed
Recognition Keywords:
- "remove"
- "delete"
- "filter"
- "nodes that satisfy"
- "exclude"
Similar Problems:
- Remove Duplicates from Sorted List (LC 83)
- Remove Duplicates from Sorted List II (LC 82)
- Delete Node in a Linked List (LC 237)
- Remove Nth Node From End (LC 19)
Key Components:
┌────────────────────────────────────────────┐
│ Dummy Node: Handle head removal │
│ Check Next: current.next.val == val │
│ Skip Node: current.next = current.next.next│
│ DON'T Move: Stay when removing │
│ Time: O(n), Space: O(1) │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "I see this requires removing nodes by value"
Step 2: "I'll use dummy node to handle head removal"
Step 3: "Check next node, skip if matches"
Step 4: "Important: don't move when removing"
Key Points to Mention:
- Dummy node simplifies head removal
- Check current.next (not current)
- Don't move pointer when removing
- Stay to check new next node
- Handle consecutive matches
- Time: O(n), Space: O(1)
Walk Through Example:
"For [1,2,6,3,6], val=6, I add a dummy node.
Check each next node.
When next is 6, skip it by: current.next = current.next.next
Don't move current - new next might also be 6!
When next is not 6, move current forward.
Return dummy.next."
Edge Cases to Mention:
✓ Empty list → returns null
✓ All nodes match → returns null
✓ No nodes match → returns original
✓ Head matches → dummy handles it
✓ Consecutive matches → stay and check
📝 Quick Revision Notes
🎯 Core Concept:
Remove Linked List Elements: Use dummy node to simplify head removal. Check current.next (not current). If matches, skip it: current.next = current.next.next. Critical: DON'T move current after removal - stay to check new next! Only move when keeping node.
⚡ Quick Implementation:
import java.util.Arrays;
import java.util.List;
class 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 static ListNode create(List<Integer> list) {
ListNode dummy = new ListNode();
ListNode curr = dummy;
for(int num : list) {
curr.next = new ListNode(num);
curr = curr.next;
}
return dummy.next;
}
public static void print(ListNode head) {
ListNode curr = head;
while (curr != null) {
System.out.print(curr.val + " -> ");
curr = curr.next;
}
System.out.println();
}
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode();
dummy.next = head;
ListNode curr = dummy;
// Intuitive on paper by having a dummy node.
// Dummy node to handle if the value to be removed is on the first on the list.
while (curr != null) {
if(curr.next != null && curr.next.val == val) {
curr.next = curr.next.next; // skip (delink) curr.next and attach next to the existing one
} else {
curr = curr.next; // else move normally
}
}
return dummy.next;
}
public static void main(String[] args) {
Solution t = new Solution();
ListNode list1 = create(Arrays.asList(1,2,6,3,4,5,6));
print(t.removeElements(list1, 6));
print(t.removeElements(create(Arrays.asList(1)), 1)); // empty
print(t.removeElements(create(Arrays.asList(1)), 6)); // 1
print(t.removeElements(create(Arrays.asList(1, 2)), 6)); // 1, 2
print(t.removeElements(create(Arrays.asList(1, 6)), 6)); // 1
print(t.removeElements(create(Arrays.asList(1, 6)), 1)); // 6
print(t.removeElements(create(Arrays.asList(1, 1, 6)), 1)); // 6
print(t.removeElements(create(Arrays.asList(1, 1, 1, 6)), 1)); // 6
print(t.removeElements(create(Arrays.asList(1, 1, 1, 6, 6)), 6)); // 1,1,1
print(t.removeElements(create(Arrays.asList(1, 1, 1, 6, 6, 6)), 6)); // 1,1,1
print(t.removeElements(create(Arrays.asList(1, 1, 1, 6, 6, 6, 7, 8)), 6)); // 1,1,1,7,8
}
}
🔑 Key Insights:
- Pattern: Dummy Node + Filter
- Dummy: Handles head removal elegantly
- Check: current.next (not current)
- Remove: Skip via current.next.next
- DON'T Move: After removal (critical!)
- Time: O(n), Space: O(1) ✓
🎪 Memory Aid:
"Dummy → Check Next → Match? Skip & Stay : Keep & Move!"
"Skip = Stay, Keep = Move!" ✨
⚠️ The Golden Rule:
When removing:
current.next = current.next.next
DON'T move current!
When keeping:
current = current.next
Move forward!
Why?
New next might also need removal!
[2 → 6 → 6 → 3]
↑
Remove first 6
[2 → 6 → 3]
↑
Stay here! Check new next (also 6)
🧪 Edge Cases
Case 1: Empty list
Input: head = null, val = 1
Output: null
Handled: Loop never runs, dummy.next = null
Case 2: All nodes match
Input: head = [7,7,7,7], val = 7
Output: null
Handled: All removed, dummy.next = null
Case 3: No nodes match
Input: head = [1,2,3], val = 4
Output: [1,2,3]
Handled: Nothing removed, returns original
Case 4: Head matches
Input: head = [6,1,2], val = 6
Output: [1,2]
Handled: Dummy allows uniform removal
Case 5: Consecutive matches
Input: head = [1,6,6,6,2], val = 6
Output: [1,2]
Handled: Stay and check after each removal
Case 6: Only head remains
Input: head = [1,6,6,6], val = 6
Output: [1]
Handled: Correctly
All handled perfectly! ✓
Related Problems
- Remove Duplicates from Sorted List (LC 83) - Similar pattern
- Remove Duplicates from Sorted List II (LC 82) - Remove all duplicates
- Delete Node in a Linked List (LC 237) - Different approach
- Remove Nth Node From End (LC 19) - Position-based removal
Happy practicing! 🎯
Note: The dummy node pattern is your best friend for any problem involving node removal! This pattern appears in dozens of linked list problems. Master the "Skip & Stay, Keep & Move" rule and you'll never get confused! 💪✨