The task is to reverse the nodes in groups of $k$ in a given linked list, where $k$ is a positive integer, and at most the length of the linked list. If any remaining nodes are not part of a group of $k$, they should remain in their original order.

It is not allowed to change the values of the nodes in the linked list. Only the order of the nodes can be modified.

Note: Use only $O(1)$ extra memory space.

Constraints:

Let n be the number of nodes in a linked list.

• $1 \leq$ k $\leq$ n $\leq 500$
• $0 \leq$ Node.value $\leq 1000$

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

A naive approach would be to use another data structure—like a stack—to reverse the nodes of the linked list and then create a new linked list with reversed nodes. Here’s how the algorithm works:

• We iterate the linked list.

• We push the $k$ group of nodes to the stack.

• We pop all $k$ numbers of nodes from the stack and add the nodes to a new linked list. When we do this, the stack will give us the reversed nodes in the $k$ group.

• We repeat the above steps for every group of size $k$ present in our linked list.

• In the end, if there are less than $k$ nodes left in the original linked list, we’ll point the tail of the reversed linked list to the ...