Reverse a linked list in groups of size k

Medium

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}