Show problems as
Classic problem #725MediumLinked List

Split Linked List in Parts

Real-world version: Dividing a Conveyor Into k Parts
Tracked in this browser only
Read Split Linked List in Parts on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstIn-Place Reversal Technique · Linked List, animated step by step

A conveyor is built from cars clipped one behind another. Each car carries a load and a clip fastened to the car behind it, and the car at the end has an empty clip. Nothing on the conveyor records how many cars it holds.

Because the harness passes plain JSON, the conveyor reaches you as chain, listing the loads in clip order starting at the front car. An empty list means there are no cars at all.

Divide the conveyor into k parts, keeping the cars in their order, so that no two parts differ in length by more than one car and no earlier part is shorter than a later one. Parts may come out empty.

Return the k parts in order, each as its own list of loads.

Examples

Example 1

Input
chain = [1, 2, 3], k = 5
Output
[[1], [2], [3], [], []]

Three cars into five parts gives a base length of nothing and a remainder of three, so the first three parts take one car each and the last two come out empty.

Example 2

Input
chain = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output
[[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]

Ten cars into three parts gives a base length of three and a remainder of one, so the first part takes four cars and the other two take three.

Example 3

Input
chain = [4, 5], k = 2
Output
[[4], [5]]

Two cars split evenly, one to each part.

Constraints

  • 0 <= chain.length <= 1000
  • 0 <= chain[i] <= 1000
  • 1 <= k <= 50

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def split_list_to_parts(chain: list[int], k: int) -> list[list[int]]:
Java
public List<List<Integer>> splitListToParts(int[] chain, int k)

More on the same topics