Remove Linked List Elements

Difficulty: Easy | Acceptance: 54.40% | Paid: No Topics: Linked List, Recursion

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.

Table of Contents

• Examples
• Constraints
• Iterative with Dummy Node
• Recursive

Examples

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

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

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

Iterative with Dummy Node

Intuition Use a dummy node that points to the head of the list. This simplifies edge cases where the head itself needs to be removed. Iterate through the list, adjusting pointers to skip nodes matching the value.

Steps

• Create a dummy node pointing to head.
• Initialize a prev pointer at dummy and curr at head.
• Traverse the list while curr is not null.
• If curr.val equals val, link prev.next to curr.next (removing curr).
• Otherwise, move prev to curr.
• Move curr to curr.next.
• Return dummy.next.

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        curr = head
        
        while curr:
            if curr.val == val:
                prev.next = curr.next
            else:
                prev = curr
            curr = curr.next
            
        return dummy.next

Complexity

• Time: O(n) where n is the number of nodes in the linked list.
• Space: O(1) as we only use a constant amount of extra space.
• Notes: The dummy node approach handles the head removal edge case elegantly without extra checks.

Recursive

Intuition Recursively process the rest of the list. If the current node’s value matches the target, return the result of the recursive call on the next node (effectively skipping the current node). Otherwise, keep the current node and link it to the processed rest of the list.

Steps

• Base case: If head is null, return null.
• Recursively call removeElements on head.next.
• If head.val equals val, return the result of the recursive call (head.next).
• Otherwise, set head.next to the result of the recursive call and return head.

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        if not head:
            return None
        
        head.next = self.removeElements(head.next, val)
        
        if head.val == val:
            return head.next
        else:
            return head

Complexity

• Time: O(n) where n is the number of nodes in the linked list.
• Space: O(n) due to the recursion stack depth.
• Notes: While elegant, the recursive approach uses stack space proportional to the list length, which could lead to a stack overflow for very large lists.