DSA problem
Reverse Nodes in k-Group
Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. k is a positive integer and is less than or equal to the length of the list. If the number of nodes is not a multiple of k, then the left-out nodes at the end should remain as they are. You may not alter the values in the list's nodes — only the node pointers may be changed.
The challenge is twofold: (1) you must reverse fixed-size windows in place, and (2) you must not reverse the final tail group if it is shorter than k. Both halves of the problem hinge on careful boundary bookkeeping.
A clean approach uses a dummy node placed before the head, plus a groupPrev pointer that always references the node just before the current group of k to be reversed. For each iteration, walk k steps from groupPrev to find the group's last node kth. If you fall off the list before completing k steps, the remaining nodes are fewer than k — stop, leaving them untouched.
Once a full group is confirmed, reverse the k nodes using the front-splice (head-insertion) variant of in-place reversal, or any standard three-pointer reversal that respects the group's right boundary. After reversal, what used to be groupPrev.next is now the tail of the reversed group; advance groupPrev to that node so the next group is reversed relative to the correct anchor. Repeat until a partial group is encountered. The total work is O(n) because every node is touched a constant number of times, and only O(1) extra space is used.
Examples
head = [1,2,3,4,5], k = 2[2,1,4,3,5]head = [1,2,3,4,5], k = 3[3,2,1,4,5]head = [1,2,3,4,5,6], k = 3[3,2,1,6,5,4]Constraints
- The number of nodes in the list is n.
- 1 <= k <= n <= 5000
- 0 <= Node.val <= 1000
- Follow up: Can you solve the problem in O(1) extra memory space?
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.