All problems

Reverse Nodes in k-Group

Hard · linked list

You are given the head of a singly linked list and an integer k. Cut the list into consecutive blocks of exactly k nodes, starting from the head, and reverse the order of the nodes inside each block. The blocks themselves stay where they are.

If the number of nodes is not a multiple of k, the last block has fewer than k nodes. That short block is left exactly as it is.

Return the head of the resulting list. The nodes you receive are ListNode objects with a val and a next; you may re-point them or change their values.

Examples

Example 1

Input: head = [1, 2, 3, 4, 5, 6, 7], k = 3

Output: [3, 2, 1, 6, 5, 4, 7]

The blocks are 1 2 3 and 4 5 6, and each is reversed. The last node, 7, is a block of one, which is shorter than 3, so it stays.

Example 2

Input: head = [10, 20, 30, 40], k = 2

Output: [20, 10, 40, 30]

Example 3

Input: head = [5, 6, 7], k = 1

Output: [5, 6, 7]

A block of one node reversed is the same node.

Constraints