Reverse a Linked List in Groups of k

MediumLinked list203 tests

You are given head, the first node of a singly linked list, and a number k.

Split the list into blocks of k nodes, starting from the first node. Reverse the order of the nodes inside each block, keep the blocks in their original order, and return the first node of the new list.

Note

The last block is also reversed, even when it has fewer than k nodes. For example, with 7 nodes and k = 3, the blocks have 3, 3 and 1 nodes; with 8 nodes and k = 3, the last block has 2 nodes and those 2 nodes swap places.
If k is equal to or larger than the length, the whole list is one block, so the whole list is reversed.
If k = 1, nothing changes.
Change the next links. Do not create new nodes.

How the input is shown

A list is written as an array of its values from first node to last node. For example, [9, 8, 7, 6] is the list 9 -> 8 -> 7 -> 6. Your function gets the first node, not the array, and k as a plain number.

Hint: reverse one block at a time with the usual three-pointer reversal, counting up to k nodes or until the list ends. Keep the last node of the previous block, and link it to the new first node of the block you just reversed.

Examples

Example 1

Input:: [5,10,15,20,25,30,35,40], 3
Output:: [15,10,5,30,25,20,40,35]

The blocks are [5, 10, 15], [20, 25, 30] and [35, 40]. Each block is reversed, including the short last block [35, 40], which becomes [40, 35].

Example 2

Input:: [9,8,7,6], 2
Output:: [8,9,6,7]

The blocks are [9, 8] and [7, 6]. Reversing each one gives 8, 9, 6, 7.

Example 3

Input:: [4,1,3], 5
Output:: [3,1,4]

k is larger than the length, so the whole list is one short block, and it is reversed.

Constraints

The list has 1 to 40 nodes.
1 <= k <= 50
0 <= val <= 99

Run checks your code against the 3 examples. Submit checks it against all 203 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.