Reverse Linked-List Groups of Actual Even Size
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Split a singly linked list into consecutive nonempty groups with intended sizes `1, 2, 3, 4, ...`. The last group contains whichever nodes remain and can be shorter than its intended size. Reverse the nodes in every group whose actual size is even, and leave the order within every odd-sized group unchanged. Return the head of the modified linked list.
```cpp
class Solution {
public:
ListNode* reverseEvenLengthGroups(ListNode* head);
};
```
### Examples
**Example 1:**
```text
List values: [1,2,3,4,5]
Output list values: [1,3,2,5,4]
Explanation: Group sizes are 1,2,2; both actual size-two groups reverse.
```
**Example 2:**
```text
List values: [2,4,6,8]
Output list values: [2,6,4,8]
Explanation: The last group has actual size one and stays unchanged.
```
### Constraints
- The list contains 1 to `10^5` nodes.
- Node values lie in `[0,10^5]`.
### Clarifying Questions
Reverse actual node links, preserving node identity and values. Decide parity from the number of nodes present, including the final short group.
```hint Inspect the structure
Before changing links, how can you locate both the actual group length and the next group's first node?
```
### Reasoning checkpoints
- Determine each group's parity from its actual number of nodes, including a short final group.
- Preserve node identities and values while producing exactly the required link order.
- Keep groups connected without losing nodes, introducing cycles or changing odd-sized groups.
### Optional extensions
How would a fixed repeating sequence of intended group sizes change the traversal?
Overview: Reverse Linked-List Groups of Actual Even Size. Partition the linked list into consecutive nonempty groups with intended sizes 1,2,3,4,...; the final group may be shorter than intended. Reverse the nodes of every group whose actual size is even, leave odd groups in order, and return the modified ListNode* head.