When working with singly linked lists, deleting nodes presents a unique challenge: how do we handle the removal of the head node? Unlike other nodes that can be removed through their predecessor, the head node has no previous node to reference.

Understanding the Challenge

In a singly linked list, removing a node typically involves updating the next pointer of the previous node. However, this approach fails for the head node since there is no preceding element. This leads to two fundamental strategies:

• Direct manipulation – Handle the head node as a special case
• Sentinel node approach – Introduce a dummy head node for unified processing

Approach 1: Using a Sentinel Node

By creating a dummy node (sentinel) that points to the original head, we can treat all nodes uniformly. Every node now has a predecessor, eliminating the need for special head-node logic.

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        # Create sentinel node pointing to head
        sentinel = ListNode(0)
        sentinel.next = head
        
        # Traverse using a pointer
        ptr = sentinel
        while ptr.next:
            if ptr.next.val == val:
                ptr.next = ptr.next.next
            else:
                ptr = ptr.next
                
        return sentinel.next

Complexity Analysis: Time complexity is O(n) as we traverse the list once. Space complexity is O(1) since we only use constant extra memory.

Approach 2: Direct Head Node Handling

This method explicitly handles head node removal by advancing the head pointer until it either points to a node with a different value or becomes null.

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        # Remove all leading nodes with target value
        while head and head.val == val:
            head = head.next
            
        # Return if list is empty
        if not head:
            return None
            
        # Process remaining nodes
        current = head
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
            else:
                current = current.next
                
        return head

Approach 3: Recursive Solution

Linked lists naturally exhibit recursive structure. The strategy involves processing the rest of the list first, then determining whether to keep or discard the current head node.

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        # Base case: empty list
        if not head:
            return None
            
        # Recursively process remaining nodes
        head.next = self.removeElements(head.next, val)
        
        # Return next node if current should be removed
        return head.next if head.val == val else head

Complexity Analysis: Time complexity remains O(n). Space complexity increases to O(n) due to the recursive call stack depth.