Scale Engineer

Remove Linked List Elements

Easy
#0191Time: O(n)Space: O(1)1 company
Patterns
Recursion
Data structures
Linked List
Companies
Arista Networks

Prompt

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]

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, 104].
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a dummy node to simplify the logic of removing nodes from the linked list. By creating a dummy node that points to the head, we can handle the edge case where the head itself needs to be removed without special handling.

Algorithm

  1. Create a dummy node and point it to the head
  2. Initialize prev pointer to dummy and current pointer to head
  3. While current is not null:
    • If current.val equals target value:
      • Skip current node by setting prev.next = current.next
    • Else:
      • Move prev to current
    • Move current to current.next
  4. Return dummy.next as the new head

Walkthrough

We create a dummy node that points to the head of the linked list. This allows us to treat all nodes uniformly, including the head node. We then iterate through the list with two pointers: prev (starting at dummy) and current (starting at head). When we find a node with the target value, we skip it by updating prev.next to point to current.next. Otherwise, we move prev forward. Finally, we return dummy.next as the new head.

class ListNode {    int val;    ListNode next;    ListNode() {}    ListNode(int val) { this.val = val; }    ListNode(int val, ListNode next) { this.val = val; this.next = next; }} public ListNode removeElements(ListNode head, int val) {    ListNode dummy = new ListNode(0);    dummy.next = head;    ListNode prev = dummy;    ListNode current = head;        while (current != null) {        if (current.val == val) {            prev.next = current.next;        } else {            prev = current;        }        current = current.next;    }        return dummy.next;}

Complexity

Time

O(n)

Space

O(1)

Trade-offs

Pros

  • Simple and intuitive logic

  • Handles edge cases (empty list, removing head) elegantly

  • Single pass through the list

  • Easy to understand and implement

Cons

  • Uses extra dummy node (minimal overhead)

  • Slightly more memory usage due to dummy node

Solutions

public class Solution { public ListNode RemoveElements ( ListNode head , int val ) { ListNode newHead = null ; ListNode newTail = null ; var current = head ; while ( current != null ) { if ( current . val != val ) { if ( newHead == null ) { newHead = newTail = current ; } else { newTail . next = current ; newTail = current ; } } current = current . next ; } if ( newTail != null ) newTail . next = null ; return newHead ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem