Split a Chain Into K Parts
MediumLinked List
Problem
A batch of n tasks, stored as a singly linked list, must be split across k workers as evenly as possible: consecutive runs of the list, sizes differing by at most 1, and earlier workers never receiving fewer tasks than later ones.
Given the head and k, cut the list into k consecutive parts and return them as an array of k arrays of values, in order. Parts may be empty when k > n.
Example 1
- Input:
- head = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
- Output:
- [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
10 = 4 + 3 + 3: the one extra task goes to the first worker.
Example 2
- Input:
- head = [1, 2, 3], k = 5
- Output:
- [[1], [2], [3], [], []]
Constraints
- 0 ≤ number of nodes ≤ 1000
- 1 ≤ k ≤ 50
- 0 ≤ node.val ≤ 1000
Hint
Show the first hint
You cannot decide where to cut without knowing n.
Walkthrough
How to approach it
01Clarify before coding
- Must parts be consecutive? Yes, cut the list without reordering.
- Who gets the extra nodes? The earliest parts.
- What if k > n? Trailing parts are empty, but there are still exactly k of them.
02Brute force
Copy every value into an array, compute the part sizes, and slice the array into k pieces.
Cost: O(n + k) time but O(n) extra space for the copy, and the list itself is never actually cut; the sizes can be computed from a count alone.
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.