Reverse linked list in fixed-size groups

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.