Remove nodes with a given value
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
You are given the head of a singly linked list and an integer `target`.
Remove **all** nodes whose value equals `target`, and return the (possibly new) head of the list.
### Input
- `head`: head node of a singly linked list (may be `null`)
- `target`: integer
### Output
- The head of the linked list after deletions
### Constraints
- Number of nodes: `0 <= n <= 10^5`
- Node values and `target` fit in 32-bit signed integer
- Must run in `O(n)` time and `O(1)` extra space (not counting the list itself)
### Examples
1) `1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6`, `target = 6` ⇒ `1 -> 2 -> 3 -> 4 -> 5`
2) `7 -> 7 -> 7`, `target = 7` ⇒ *(empty list)*
3) *(empty list)*, `target = 1` ⇒ *(empty list)*
Quick Answer: This question evaluates proficiency in singly linked list manipulation, specifically pointer handling and in-place node removal, and falls under the Coding & Algorithms domain.
You are given the head of a singly linked list and an integer target.
Remove all nodes whose value equals target, and return the possibly new head of the list.
For this coding environment, the linked list is represented as a Python list of node values in order. An empty list [] represents a null head. Return the final linked list in the same format.
Example:
- head = [1, 2, 6, 3, 4, 5, 6], target = 6
- result = [1, 2, 3, 4, 5]
Constraints
- 0 <= len(head) <= 10^5
- Each node value and target fits in a 32-bit signed integer
- The intended linked list algorithm should run in O(n) time
- Use O(1) auxiliary space for the linked list pointer manipulation
Examples
Input: ([1, 2, 6, 3, 4, 5, 6], 6)
Expected Output: [1, 2, 3, 4, 5]
Explanation: Both nodes with value 6 are removed, including the one at the tail.
Input: ([7, 7, 7], 7)
Expected Output: []
Explanation: Every node matches the target, so the result is an empty list.
Input: ([], 1)
Expected Output: []
Explanation: The input list is already empty, so nothing changes.
Input: ([5], 5)
Expected Output: []
Explanation: The single node matches the target and is removed.
Input: ([-1, 2, -1, 3, -1], -1)
Expected Output: [2, 3]