203. Remove Linked List Elements
Model: qwen2.5-coder:14b
Topics: Linked List
FAANG asked: 1
Acceptance rate: 39.5%
Problem Breakdown
The problem requires removing all nodes from a singly linked list that have a specific value val. The input is the head of the linked list and the integer val to be removed. The output should be the new head of the modified linked list after removing all nodes with the given value.
Inputs:
head: The head node of the singly linked list.val: An integer representing the value of nodes to be removed.
Outputs:
- The head node of the modified linked list.
Implicit Constraints and Edge Cases:
- Empty List: If the input list is empty (
headisNone), the function should returnNone. - All Nodes with Target Value: If all nodes in the list have the value
val, the function should return an empty list. - Nodes at the Beginning/End/Middle: The node to be removed could be at the beginning, end, or middle of the list.
Intuition
A brute-force approach would involve iterating through the linked list and removing nodes with the target value by adjusting pointers. However, this approach can be inefficient if multiple consecutive nodes need to be removed, as it may require multiple pointer adjustments for each node.
The key insight is to use a dummy node that points to the head of the list. This allows us to handle edge cases where the head itself needs to be removed without special handling. By iterating through the list with a single pass and adjusting pointers appropriately, we can efficiently remove all nodes with the target value.
Approach
- Create a Dummy Node: Initialize a dummy node that points to the head of the list. This helps in easily removing the head if it needs to be deleted.
- Initialize a Pointer: Use a pointer
currentstarting from the dummy node. - Iterate Through the List: Traverse the linked list using the
currentpointer. - Remove Nodes with Target Value:
- If the next node’s value is equal to
val, skip it by adjusting thenextpointer of the current node to point to the node after the next node. - Otherwise, move the
currentpointer one step forward.
- If the next node’s value is equal to
- Return the New Head: After processing all nodes, return the
nextnode of the dummy node as the new head of the list.
Complexity Analysis
- Time Complexity: O(n), where n is the number of nodes in the linked list. We traverse each node once.
- Space Complexity: O(1). We use a constant amount of extra space for the dummy node and pointers.
Solution
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 points to the head of the list
dummy = ListNode(0)
dummy.next = head
# Initialize a pointer starting from the dummy node
current = dummy
# Iterate through the linked list
while current.next:
if current.next.val == val:
# Skip the node with the target value
current.next = current.next.next
else:
# Move to the next node
current = current.next
# Return the new head of the modified list
return dummy.next
Edge Cases Handled
- Empty List: If
headisNone, the function returnsNone. - All Nodes with Target Value: The dummy node ensures that if all nodes have the target value, the function returns an empty list.
- Nodes at the Beginning/End/Middle: The approach handles nodes to be removed at any position in the list without special cases.