Start practising

Remove Linked List Elements

Easy Linked List Dummy Node Pattern Original on LeetCode

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, 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

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 Java code.

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.
Java
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.
Java
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.