Remove Linked List Elements

Easy
1988.

Remove Linked List Elements

EasyLinked ListRecursionAmazonMicrosoft

Remove Linked List Elements is an easy coding problem on recursion, asked in Amazon and Microsoft interviews.

Given the head of a singly linked list and an integer value, remove every node whose value equals value, and return the head of the resulting list.

Example 1

Input
head = [1,2,6,3,4,5,6], value = 6
Output
[1,2,3,4,5]

Example 2

Input
head = [], value = 1
Output
[]

Example 3

Input
head = [7,7,7,7], value = 7
Output
[]
Explanation
Every node goes, including the head — the answer is the empty list.

Constraints

  • The number of nodes in the list is in the range [0, 10^4]
  • 1 <= Node.val <= 50
  • 0 <= value <= 50
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} value
 * @return {ListNode}
 */
var removeElements = function(head, value) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in
AI InterviewGet started

Remove Linked List Elements — Solution in Python, Java & C++

Remove Linked List Elements solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on recursion.

Remove Linked List Elements is an easy coding problem on recursion, asked in Amazon and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Recursion
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given the head of a singly linked list and an integer value, remove every node whose value equals value, and return the head of the resulting list.

Example 1

Input: head = [1,2,6,3,4,5,6], value = 6
Output: [1,2,3,4,5]

Example 2

Input: head = [], value = 1
Output: []

Example 3

Input: head = [7,7,7,7], value = 7
Output: []
Explanation: Every node goes, including the head — the answer is the empty list.

Constraints

  • The number of nodes in the list is in the range [0, 10^4]
  • 1 <= Node.val <= 50
  • 0 <= value <= 50

Hints for Remove Linked List Elements

  1. Hint 1

    Removing a node means pointing its predecessor past it — but the head has no predecessor.

  2. Hint 2

    Put a dummy node in front of the head, so every real node has one.

  3. Hint 3

    Walk with cur starting at the dummy: if cur.next must go, skip it and stay; otherwise step forward. Return dummy.next.

How to solve Remove Linked List Elements

Deleting from a singly linked list is done from the predecessor. A dummy node before the head gives every node a predecessor, so leading matches need no special case.

Approach

  1. Create dummy with dummy.next = head and set cur = dummy.
  2. While cur.next exists: if cur.next.val == value, set cur.next = cur.next.next; otherwise move cur = cur.next.
  3. Return dummy.next.

Why it works

cur always points at a node that is kept (the dummy or a non-matching node), and each matching successor is unlinked before cur moves on. Every node is examined exactly once as cur.next.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Returning head instead of dummy.next is wrong when the head itself is removed.
  • After unlinking, do not advance — consecutive matches would be skipped.

Reference solution

Python

from typing import Optional

def removeElements(head: Optional[ListNode], value: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    cur = dummy
    while cur.next:
        if cur.next.val == value:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return dummy.next

Java

public static ListNode removeElements(ListNode head, int value) {
    ListNode dummy = new ListNode(0, head), cur = dummy;
    while (cur.next != null) {
        if (cur.next.val == value) cur.next = cur.next.next;
        else cur = cur.next;
    }
    return dummy.next;
}

C++

ListNode* removeElements(ListNode* head, int value) {
    ListNode dummy(0, head);
    ListNode* cur = &dummy;
    while (cur->next) {
        if (cur->next->val == value) cur->next = cur->next->next;
        else cur = cur->next;
    }
    return dummy.next;
}

JavaScript

var removeElements = function(head, value) {
    var dummy = new ListNode(0, head), cur = dummy;
    while (cur.next !== null) {
        if (cur.next.val === value) cur.next = cur.next.next;
        else cur = cur.next;
    }
    return dummy.next;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 40 recursion problems · the whole catalogue

Learn the technique: Recursion