Reference: LeetCode

Difficulty: Medium

## Problem

Given a (singly) linked list with head node

`root`

, write a function to split the linked list into`k`

consecutive linked list “parts”.

The length of each part should be as equal as possible: no two parts should have a size differing by more than`1`

. This may lead to some parts being null.

The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later.

Return a List of ListNode’s representing the linked list parts that are formed.

**Note:**

- The length of
`root`

will be in the range`[0, 1000]`

. - Each value of a node in the input will be an integer in the range
`[0, 999]`

. `k`

will be an integer in the range`[1, 50]`

.

**Example:**

1 | Input: root = [1, 2, 3], k = 5 |

## Analysis

**Methods:**

- In-Place
- The length of the list is
`n`

. - There are
`k`

groups, so the`result`

should initialized with size`k`

. - The width of each part is
`width`

which is equal to`n / k`

. - We also notice that the width of some parts at the beginning should
`width + 1`

. The number of these parts is`n % k`

.1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34public ListNode[] splitListToParts(ListNode root, int k) {

ListNode[] result = new ListNode[k];

int n = getLength(root);

int width = n / k;

int numOfOneMore = n % k;

ListNode p = root;

// 1 2 3 4 5

// -------

// p p

for (int i = 0; i < k; ++i) {

result[i] = p;

int count = (i < numOfOneMore) ? width + 1 : width;

while (count > 1) {

p = p.next;

count -= 1;

}

if (p != null) {

ListNode nextTemp = p.next;

p.next = null;

p = nextTemp;

}

}

return result;

}

private int getLength(ListNode root) {

int count = 0;

while (root != null) {

root = root.next;

count += 1;

}

return count;

}**Time:**$O(N)$**Space:**$O(k)$ the size of the`result`

.

- The length of the list is