Reverse Nodes in k-Group
Hard · Linked Lists · Linked List · Recursion
Problem
Given the head of a linked list and a positive integer k, reverse the nodes in consecutive groups of k. If fewer than k nodes remain at the end, leave that final group in its original order.
Rearrange the nodes themselves rather than only changing their values, and return the head of the modified list.
Can you do it with O(1) extra memory?
Examples
Input: head = [1,2,3,4,5,6,7,8], k = 3 Output: [3,2,1,6,5,4,7,8]
Two full groups of three are reversed; the leftover 7, 8 stays as it is.
Input: head = [9,8,7], k = 1 Output: [9,8,7]
Reversing a group of one changes nothing.
Constraints
- The list has n nodes.
- 1 <= k <= n <= 5000
- 0 <= Node.val <= 1000
Approaches
- Baseline: collect the nodes, relink in group order — time O(n), space O(n)
Follow-up
What if the short last group should be reversed too, or only every other group? Both keep the same stitching and change only when to reverse: see the use cases “Reverse every group, short one included” and “Reverse every other group”.
Related problems
Start free on Cariara · Coding problems · System design studio
