Solution: Split Linked List in Parts

Statement

You are given head of a singly linked list and an integer, k. Your task is to split the linked list into k consecutive parts.

• Each part should have a size as equal as possible, with the difference between any two parts being at most $1$.

• If the list cannot be evenly divided, the earlier parts should have more nodes than the later ones.

• Any parts that cannot be filled with nodes should be represented as NULL.

• The parts must appear in the same order as in the input-linked list.

Return an array of the k parts, maintaining the specified conditions.

Constraints:

• The number of nodes in the list is in the range $[0, 10^{3}]$.

• $0 \leq$ Node.data $\leq 10^{3}$

• $1 \leq$ k $\leq 50$

Solution

The essence of this solution lies in splitting a singly linked list into k parts while ensuring that each part's size differs by at most one node. The solution maintains the order of the original list and distributes nodes evenly, ensuring earlier parts are larger if necessary. The solution involves calculating the sizes of each part, iterating through the list, and creating new sub-lists for each part.

Now, let’s see the steps of the solution:

1. We create an empty 2D array, ans of size k.

2. We then initialize size = 0 and traverse the linked list using a pointer current, incrementing size for each node encountered. This gives the total number of nodes in the list.

3. We calculate the minimum size for each part, split, and the number of extra nodes, remaining that cannot be evenly distributed using the formulas below: