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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Remove Linked List Elements

Difficulty: Easy

Problem 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.

Key Insights

  • We need to traverse the linked list and remove nodes with the specified value.
  • The head of the list might also need to be removed, which requires handling the head pointer carefully.
  • We can use a dummy node to simplify the removal process and avoid edge cases with the head.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list, since we need to inspect each node once. Space Complexity: O(1), as we are using a constant amount of space regardless of the input size.

Solution

To solve this problem, we will use a two-pointer approach with a dummy node:

  1. Create a dummy node that points to the head of the list.
  2. Use a current pointer to iterate through the list.
  3. For each node, check if its value equals the specified value. If it does, skip it by adjusting pointers; otherwise, move the current pointer forward.
  4. Finally, return the next of the dummy node as the new head of the modified list.

Code Solutions

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeElements(head: ListNode, val: int) -> ListNode:
    # Create a dummy node
    dummy = ListNode(0)
    dummy.next = head
    current = dummy
    
    # Traverse the list
    while current.next:
        if current.next.val == val:
            # Skip the node
            current.next = current.next.next
        else:
            # Move to the next node
            current = current.next
    
    return dummy.next
← Back to All Questions