Remove Even-Positioned Nodes from a Linked List

## Problem A singly linked list is represented for console input by an array of its node values in head-to-tail order. Remove every node in an even one-based position and return the remaining node values in traversal order. For `values = [1, 2, 3, 4, 5]`, positions `2` and `4` are removed, producing `[1, 3, 5]`. ### Function Contract Implement `removeEvenPositions(values)` and return an array containing the values from the odd one-based positions. ### Constraints & Assumptions - `0 <= len(values) <= 1,000,000`. - Node values are signed 32-bit integers and may repeat. - The input array is the console serialization of an acyclic singly linked list. - Returning a new array is allowed for the serialized console result. In a pointer-based linked-list implementation, the corresponding operation can relink nodes in place without allocating a second list. - Return an empty array for an empty list. ### Clarifying Questions to Ask - Are positions counted from one? Yes; the head is position one and remains. - Should removed values be returned? No. - Does the console receive pointer nodes? No; it receives the list's values in traversal order. - What happens to a two-node list? Only the first value remains. ```hint Keep every other value Traverse from the first value and append positions `1, 3, 5, ...` to the serialized result. ``` ### Example ```text input = [10, 20, 30, 40, 50, 60] output = [10, 30, 50] ``` ### Evaluation Focus - Uses one-based positional semantics. - Handles zero, one, and two values correctly. - Preserves the relative order of all retained values. - Runs in `O(n)` time and uses `O(n)` output space; aside from the returned serialization, it uses `O(1)` auxiliary state. ### Extensions to Discuss 1. How would you remove every k-th node? 2. How would the implementation differ for an immutable list? 3. How would a pointer-based implementation relink nodes in place?