algoadvance

Given the head of a linked list and an integer val, remove all the nodes of the linked list that have 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]
  2. Input: head = [], val = 1 Output: []
  3. Input: head = [7,7,7,7], val = 7 Output: []

Clarifying Questions

To solve this problem accurately, here are a few clarifications:

  1. Can the linked list be empty?
    • Yes, if the linked list is empty, return an empty list.
  2. Are all node values positive integers?
    • Yes, it is typically assumed unless stated otherwise.
  3. Should we consider any specific constraints on time or space complexity?
    • The solution should be efficient, ideally O(n) time complexity where n is the number of nodes in the linked list.

Code

Here’s the Python implementation of the solution:

# Definition for singly-linked list.
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 that helps with edge cases such as deleting the head node
    dummy = ListNode(next=head)
    current = dummy

    # Traverse the list
    while current and current.next:
        if current.next.val == val:
            # Remove the node by pointing to the next of next node
            current.next = current.next.next
        else:
            current = current.next
    
    # Return the new list head, which is the next of dummy node
    return dummy.next

# Example Usage
def build_linked_list(values):
    dummy = ListNode()
    current = dummy
    for value in values:
        current.next = ListNode(val=value)
        current = current.next
    return dummy.next

def print_linked_list(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    print(result)

# Testing the function
head = build_linked_list([1, 2, 6, 3, 4, 5, 6])
print_linked_list(removeElements(head, 6))  # Output: [1, 2, 3, 4, 5]

Strategy

  1. Dummy Node: Creating a dummy node, whose next points to the head, allows us to handle cases where the head itself might need to be removed without special conditions.
  2. Traversal: Traverse the list with a pointer current. Every time a node with current.next.val == val is found, remove it by pointing current.next to current.next.next.
  3. Efficiency: This ensures that every node is visited once, making our solution O(n) in time complexity.
  4. Edge Cases: Handles cases where the list is empty, or all elements are the value to be removed, effectively returning the correct node or an empty list.

Time Complexity

This should effectively solve the problem of removing elements from a linked list.

Try our interview co-pilot at AlgoAdvance.com