## Problem Given the head of a singly linked list, remove every node in an even one-based position and return the new head. Preserve the relative order of the remaining nodes. ### Function Contract Implement `removeEvenPositions(head)`. For `a -> b -> c -> d -> e`, positions `2` and `4` are removed, producing `a -> c -> e`. ### Constraints & Assumptions - The list contains at most `1,000,000` nodes. - Node values may repeat. - Modify links in place; do not allocate a second list. - Return `null` for an empty list. ### Clarifying Questions to Ask - Are positions counted from one? Yes; the head is position one and remains. - Should removed nodes be returned? No. - Must the original list structure be preserved? No, in-place relinking is required. - What happens to a two-node list? Only the head remains. ```hint Skip one successor at a time For each retained odd-position node, link it directly to the node two steps ahead, then advance to that retained node. ``` ### 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 nodes without dereferencing a missing successor. - Does not lose the rest of the list while changing a link. - Runs in `O(n)` time and `O(1)` extra space. ### Extensions to Discuss 1. How would you remove every k-th node? 2. How would the implementation differ for an immutable list? 3. What extra steps are needed in a language with manual memory management?