Remove Linked List Elements

EASY

Description

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

Approaches

Checkout 3 different approaches to solve Remove Linked List Elements. Click on different approaches to view the approach and algorithm in detail.

Iterative Approach with Dummy Node

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

Create a dummy node and point it to the head
Initialize prev pointer to dummy and current pointer to head
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
Return dummy.next as the new head

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 Analysis

Time Complexity: O(n)Space Complexity: O(1)

Pros and Cons

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

Code Solutions

Checking out 4 solutions in different languages for Remove Linked List Elements. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Remove Linked List Elements

Patterns:

Recursion

Data Structures:

Linked List

Companies:

Arista Networks |