Remove Linked List Elements
Remove Linked List Elements is a easy linked list problem solved with the dummy node pattern pattern.
The best approach, optimal (dummy node), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from without a dummy node up.
Problem
Given the head of a linked list and a value val, remove every node whose value equals val and return the new head.
Examples
Example 1
- Input
head = [6, 1, 6, 2, 6], val = 6- Output
[1, 2]- Why
- The head itself is removed, which is why a dummy node helps.
Example 2
- Input
head = [3, 3], val = 3- Output
[]
Constraints
- The list has
0to10^4nodes. 1 <= Node.val <= 50,0 <= val <= 50
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Without a dummy node | O(n) | O(1) |
| Optimal (dummy node) | O(n) | O(1) |
1Without a dummy node
O(n)O(1)First skip matching nodes at the head, then unlink matching nodes after it. It works, but needs a special case for the head.
- While head != null and head.val == val, head = head.next.
- Walk cur; if cur.next.val == val, cur.next = cur.next.next, else advance.
class Solution {
public ListNode removeElements(ListNode head, int val) {
while (head != null && head.val == val) head = head.next;
ListNode cur = head;
while (cur != null && cur.next != null) {
if (cur.next.val == val) cur.next = cur.next.next;
else cur = cur.next;
}
return head;
}
}class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
while head and head.val == val:
head = head.next
cur = head
while cur and cur.next:
if cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return headclass Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
while (head != nullptr && head->val == val) head = head->next;
ListNode* cur = head;
while (cur != nullptr && cur->next != nullptr) {
if (cur->next->val == val) cur->next = cur->next->next;
else cur = cur->next;
}
return head;
}
};function removeElements(head, val) {
while (head !== null && head.val === val) head = head.next;
let cur = head;
while (cur !== null && cur.next !== null) {
if (cur.next.val === val) cur.next = cur.next.next;
else cur = cur.next;
}
return head;
}2Optimal (dummy node)
O(n)O(1)Attach a dummy node before the head. Every real node now has a predecessor, so one loop handles all cases. Return dummy.next.
- dummy.next = head; cur = dummy.
- If cur.next.val == val unlink it, else move cur forward.
- Return dummy.next.
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0, head), cur = dummy;
while (cur.next != null) {
if (cur.next.val == val) cur.next = cur.next.next;
else cur = cur.next;
}
return dummy.next;
}
}class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
cur = dummy
while cur.next:
if cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.nextclass Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummy = new ListNode(0, head);
ListNode* cur = dummy;
while (cur->next != nullptr) {
if (cur->next->val == val) cur->next = cur->next->next;
else cur = cur->next;
}
return dummy->next;
}
};function removeElements(head, val) {
const dummy = new ListNode(0, head);
let cur = dummy;
while (cur.next !== null) {
if (cur.next.val === val) cur.next = cur.next.next;
else cur = cur.next;
}
return dummy.next;
}Edge cases to test
- Empty list
- Head nodes to remove
- Consecutive nodes to remove
Hints
Hint 1
Put a dummy node before the head so removing the head is no different from removing any other node.
FAQ
What is the best time complexity for Remove Linked List Elements?
Optimal (dummy node) runs in O(n) time and O(1) extra space.
Which pattern does Remove Linked List Elements use?
It is a linked list problem that uses the dummy node pattern pattern. Other problems with the same pattern: Delete Nodes From Linked List Present in Array, Merge Two Sorted Lists, Rotate List.
Is there a brute force solution for Remove Linked List Elements?
Yes. Without a dummy node takes O(n) time and O(1) space. First skip matching nodes at the head, then unlink matching nodes after it.
Which edge cases should I test for Remove Linked List Elements?
Empty list; Head nodes to remove; Consecutive nodes to remove.