Reverse a linked list in groups of size k
Problem
Reverse the nodes of the list k at a time and return the new head. In the GfG version a final group shorter than k is also reversed. In the LeetCode version it is left as it is — confirm which one is meant.
Example 1
Input: 1 → 2 → 3 → 4 → 5, k = 2 Output: 2 → 1 → 4 → 3 → 5
Example 2
Input: 1 → 2 → 3 → 4 → 5, k = 3 Output: 3 → 2 → 1 → 4 → 5 (LeetCode) or 3 → 2 → 1 → 5 → 4 (GfG)
Also asked as: Reverse a Linked List in group of Given Size
Test cases
Case 1
Input: [1,2,3,4,5], 2 Expected: [2,1,4,3,5]
Case 2
Input: [1,2,3,4,5], 3 Expected: [3,2,1,4,5]
Case 3
Input: [1,2,3,4,5,6], 3 Expected: [3,2,1,6,5,4]
View solutionHide solution1 approach
1. Recursive per group
Time O(n)Space O(n / k) recursion
Reverse the first k nodes; recurse on the rest and attach it to the (now) tail of the reversed group.
function reverseKGroup(head, k) { let node = head, count = 0; while (node && count < k) { node = node.next; count++; } if (count < k) return head; // fewer than k left: keep as is let prev = reverseKGroup(node, k), cur = head; for (let i = 0; i < k; i++) { const next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev;}