You get the head of a linked list and a whole number k.
Cut the list into blocks of k nodes, starting from the front. Reverse the order of the nodes inside each block. Return the head of the new list.
The last block can have fewer than k nodes. Leave that block as it is.
Change only the next links. Each value stays in its own node.
Example 1:
Input: head = [10,20,30,40,50,60,70], k = 3 Output: [30,20,10,60,50,40,70] Explanation: The blocks are [10,20,30], [40,50,60] and [70]. The first two blocks are reversed. [70] has fewer than 3 nodes, so it stays as it is.
Example 2:
Input: head = [6,1,9,2], k = 2 Output: [1,6,2,9] Explanation: The blocks are [6,1] and [9,2]. In each block, the two nodes swap places.
Example 3:
Input: head = [5,8,3], k = 3 Output: [3,8,5] Explanation: k is the length of the list. So the whole list is one block, and all of it is reversed.
Constraints:
- 1 to 5,000 nodes.
kis from 1 to the number of nodes.- Each value is from -10,000 to 10,000.
Your solution should run in O(n) time for n nodes, with O(1) extra space.
First count the nodes. Then you know how many full blocks there are. Only those get reversed.
Reverse one block as in Reverse Linked List, but stop after
k nodes. The block's first node becomes its last node. Link it to the node right after the block. Then the node before the block must point to the block's new first node. A placeholder node in front of head gives the first block a node before it too.
Each node is counted once and moved once: O(n) time.
Only a few pointers are kept, however long the list is: O(1) extra space.
Copying the nodes into a list first would work too, but it takes O(n) extra space.
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
