Flip Blocks From the Tail
HardLinked List
Problem
A loading dock forms crates of k consecutive items, but it counts crates from the end of the line: the last k items form a crate, the k before them another, and so on. Any leftover items, fewer than k, are at the front and are not crated.
Given the head and k, reverse the nodes of every complete crate (relinking nodes, not values), keep the leftover front segment as is, and return the head. Use O(1) extra space.
Example 1
- Input:
- head = [1, 2, 3, 4, 5, 6, 7, 8], k = 3
- Output:
- [1, 2, 5, 4, 3, 8, 7, 6]
From the end, crates are [6, 7, 8] and [3, 4, 5]; [1, 2] is the leftover front.
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
Where do the crates start if you count them from the end? It depends only on n and k.
Walkthrough
How to approach it
01Clarify before coding
- Where is the incomplete group? At the front, because crates are counted from the tail.
- What if n is a multiple of k? There is no leftover; every block is reversed.
- Can I reverse the whole list, process, and reverse back? Possible, but there is a simpler idea.
02Brute force
Reverse the entire list, reverse in blocks of k from the head, leaving the incomplete last block, then reverse the leftover and the entire list again so everything lands right.
Cost: O(n) time and O(1) space, but several full passes and fiddly bookkeeping where bugs hide; storing nodes in an array instead costs O(n) space.
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.