Remove Linked List Elements

Easy Linked List Dummy Node Pattern Original on LeetCode

Reported atFreshworks

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 0 to 10^4 nodes.
  • 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.

00:00
Testcase

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.

ApproachTimeSpace
Without a dummy nodeO(n)O(1)
Optimal (dummy node)O(n)O(1)

1Without a dummy node

TimeO(n)
SpaceO(1)

First skip matching nodes at the head, then unlink matching nodes after it. It works, but needs a special case for the head.

  1. While head != null and head.val == val, head = head.next.
  2. 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;
    }
}

2Optimal (dummy node)

TimeO(n)
SpaceO(1)

Attach a dummy node before the head. Every real node now has a predecessor, so one loop handles all cases. Return dummy.next.

  1. dummy.next = head; cur = dummy.
  2. If cur.next.val == val unlink it, else move cur forward.
  3. 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;
    }
}

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.