We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Remove Linked List Elements

Number: 203

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Microsoft, Meta, Bloomberg, Adobe, Apple

Problem Description

Given the head of a linked list and an integer val, remove all the nodes that have Node.val equal to val, and return the new head of the modified linked list.

Key Insights

  • Utilize a dummy node to simplify the removal process, especially if the head or several initial nodes need to be removed.
  • Traverse the list using a pointer. For each node, check if its next node has the matching val.
  • If a node to be removed is found, adjust the pointer to skip it.
  • The algorithm processes each node exactly once, ensuring efficiency.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list. Space Complexity: O(1), as no additional data structures are used beyond a few pointers.

Solution

The solution employs an iterative approach with a dummy node preceding the head of the list. This dummy node helps handle edge cases seamlessly, such as when the first node (or several beginning nodes) needs to be removed. By iterating through the list, we check if the next node’s value equals the target value, and if so, we skip it. The list is thus re-linked without the undesired nodes, and the new head (dummy.next) is returned.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val  # Node's value
        self.next = next  # Pointer to the next node

def removeElements(head: ListNode, val: int) -> ListNode:
    dummy = ListNode(0)  # Create a dummy node to handle edge cases
    dummy.next = head  # Link dummy node to the head of the list
    current = dummy  # Set the pointer starting at the dummy node
    while current.next:
        if current.next.val == val:
            # Skip over the node with the target value
            current.next = current.next.next
        else:
            # Move to the next node in the list
            current = current.next
    return dummy.next  # Return the new head of the list
← Back to All Questions