Flip in Blocks of K
HardLinked List
Problem
A packing line groups items into crates of exactly k consecutive items, and each full crate is unloaded in reverse order. Items left over at the end, fewer than k, are not crated and keep their order.
Given the head of the item list and k, reverse the nodes of every complete block of k consecutive nodes and return the head. Relink nodes; do not just swap values. Use O(1) extra space.
Example 1
- Input:
- head = [1, 2, 3, 4, 5, 6, 7, 8], k = 3
- Output:
- [3, 2, 1, 6, 5, 4, 7, 8]
Blocks [1, 2, 3] and [4, 5, 6] are reversed; [7, 8] is incomplete and stays.
Example 2
- Input:
- head = [1, 2, 3, 4], k = 2
- Output:
- [2, 1, 4, 3]
Constraints
- 1 ≤ number of nodes ≤ 5000
- 1 ≤ k ≤ number of nodes
- 0 ≤ node.val ≤ 1000
Hint
Show the first hint
Each block is a small reverse-a-list problem. The real work is wiring each reversed block to the previous one and to the rest.
Walkthrough
How to approach it
01Clarify before coding
- What happens to a final incomplete block? It stays in its original order.
- Can k be 1? Yes: the list is unchanged. Can k equal n? Yes: the whole list is reversed.
- Is O(n) extra memory acceptable? No, aim for O(1).
02Brute force
Copy the nodes into an array, reverse each complete chunk of k positions in the array, and relink all nodes in the new order.
Cost: O(n) time but O(n) extra space for the array; the in-place version is what the problem asks for.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.