Reverse linked list in fixed-size groups
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
### Problem
You are given the head of a singly linked list and an integer `k` (`k >= 1`).
Reverse the nodes of the list **in-place** in groups of size `k`:
- The nodes in each consecutive block of `k` nodes should be reversed as a group.
- If the number of nodes at the end of the list is **less than** `k`, leave those nodes in their original order.
- Return the new head of the modified list.
You may assume the list nodes are defined in the usual way, for example:
- In C++:
- `struct ListNode { int val; ListNode* next; };`
- In Java:
- `class ListNode { int val; ListNode next; }`
#### Example
Input list (values):
`1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7`, and `k = 3`
Output list should be:
`3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7`
- The first 3 nodes `(1, 2, 3)` are reversed to `(3, 2, 1)`.
- The next 3 nodes `(4, 5, 6)` are reversed to `(6, 5, 4)`.
- The last node `7` is fewer than `k` nodes, so it stays as is.
#### Constraints
- Number of nodes `n` can be up to around `10^5`.
- You must operate in-place using `O(1)` extra space (excluding recursion stack if you choose a recursive solution).
- Aim for `O(n)` time.
Describe your algorithm and then implement a function that performs this transformation.
Quick Answer: This question evaluates proficiency with singly linked list manipulation, pointer/reference management, in-place group operations, and complexity reasoning including time and constant extra space.
Linked lists are represented as value arrays. Reverse each full group of k values and leave a short tail unchanged.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([1,2,3,4,5,6,7], 3)
Expected Output: [3, 2, 1, 6, 5, 4, 7]
Explanation: Reverse full groups of size 3.
Input: ([1,2,3], 1)
Expected Output: [1, 2, 3]
Explanation: k=1 leaves list unchanged.
Input: ([1,2], 3)
Expected Output: [1, 2]
Explanation: Short final group is not reversed.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.