Reverse nodes in even-length linked-list groups
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
### Problem
Given the head of a singly linked list, you will traverse the list in **contiguous groups** of increasing size: the 1st group has size 1, the 2nd group has size 2, the 3rd group has size 3, and so on.
For each group:
- If the **actual number of nodes** in that group is **even**, reverse the nodes in that group.
- If the actual number of nodes in that group is **odd**, leave the group as-is.
Note: The final group may contain fewer nodes than its intended size; its **actual length** determines whether it should be reversed.
Return the head of the modified linked list.
### Input/Output
- **Input:** `head` — head node of a singly linked list.
- **Output:** head of the updated list after performing the operations above.
### Example
List: `1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9`
- Group sizes: 1 | 2 | 3 | 4 ...
- Groups: `[1]`, `[2,3]`, `[4,5,6]`, `[7,8,9]` (last group has length 3)
- Reverse even-length groups only: `[2,3]` is even → becomes `[3,2]`; others unchanged
Result: `1 -> 3 -> 2 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9`
### Constraints (typical)
- Number of nodes `n`: `1 <= n <= 10^5`
- Node values can be any integers (do not affect the logic).
- Aim for `O(n)` time and `O(1)` extra space (excluding recursion stack).
Quick Answer: This question evaluates proficiency with singly linked list manipulation, in-place group operations (including conditional group reversal based on group length), pointer handling, and reasoning about linear time and constant extra space constraints.