Remove Linked List Elements

1. Create a dummy node and point it to the head
2. Initialize prev pointer to dummy and current pointer to head
3. While current is not null:
   • If current.val equals target value:
     • Skip current node by setting prev.next = current.next
   • Else:
     • Move prev to current
   • Move current to current.next
4. Return dummy.next as the new head

We create a dummy node that points to the head of the linked list. This allows us to treat all nodes uniformly, including the head node. We then iterate through the list with two pointers: prev (starting at dummy) and current (starting at head). When we find a node with the target value, we skip it by updating prev.next to point to current.next. Otherwise, we move prev forward. Finally, we return dummy.next as the new head.

1class ListNode {2    int val;3    ListNode next;4    ListNode() {}5    ListNode(int val) { this.val = val; }6    ListNode(int val, ListNode next) { this.val = val; this.next = next; }7}8 9public ListNode removeElements(ListNode head, int val) {10    ListNode dummy = new ListNode(0);11    dummy.next = head;12    ListNode prev = dummy;13    ListNode current = head;14    15    while (current != null) {16        if (current.val == val) {17            prev.next = current.next;18        } else {19            prev = current;20        }21        current = current.next;22    }23    24    return dummy.next;25}

1. Remove all nodes from the beginning that match the target value
2. If list becomes empty, return null
3. Initialize prev to head and current to head.next
4. While current is not null:
   • If current.val equals target value:
     • Skip current node by setting prev.next = current.next
   • Else:
     • Move prev to current
   • Move current to current.next
5. Return the updated head

First, we handle the special case where consecutive nodes at the beginning (including head) need to be removed. We keep moving the head pointer forward until we find a node that doesn't match the target value or reach the end. Then, we use two pointers to traverse the rest of the list: prev and current. When we find a node to remove, we update prev.next to skip the current node.

1public ListNode removeElements(ListNode head, int val) {2    // Handle nodes at the beginning that need to be removed3    while (head != null && head.val == val) {4        head = head.next;5    }6    7    // If list becomes empty8    if (head == null) {9        return null;10    }11    12    ListNode prev = head;13    ListNode current = head.next;14    15    while (current != null) {16        if (current.val == val) {17            prev.next = current.next;18        } else {19            prev = current;20        }21        current = current.next;22    }23    24    return head;25}

1. Base case: if head is null, return null
2. Recursively call removeElements on head.next
3. Set head.next to the result of recursive call
4. If head.val equals target value:
   • Return head.next (skip current node)
5. Else:
   • Return head (keep current node)

The recursive approach works by first recursively calling the function on the next node to get the processed tail of the list. Then, we check if the current node's value matches the target value. If it matches, we return the processed tail (effectively removing the current node). If it doesn't match, we connect the current node to the processed tail and return the current node.

1public ListNode removeElements(ListNode head, int val) {2    // Base case: empty list3    if (head == null) {4        return null;5    }6    7    // Recursively process the rest of the list8    head.next = removeElements(head.next, val);9    10    // If current node should be removed, return the processed tail11    // Otherwise, return current node connected to processed tail12    return head.val == val ? head.next : head;13}