LeetCode: Split Linked List in Parts Solution

Approach

Let n be the size of the list

Each part of k parts will have n / k elements plus extra 1 element if the part index is less than n % k

Naming explanation

1dividend = divisor * quotient + remainder
2
3eg. 10 = 3 * 3 + 1

Implementation

1var splitListToParts = function (head, k) {
2  let n = 0
3  let iter = head
4  let res = Array(k).fill(null)
5
6  for (; iter; iter = iter.next, n++) {}
7
8  // naming explanation:
9  // dividend = divisor * quotient + remainder
10  let quotient = Math.floor(n / k)
11  let remainder = n % k
12
13  iter = head
14
15  for (let part = 0; part < k && iter; part++) {
16    let partSize = quotient + (part < remainder ? 1 : 0)
17
18    // init first element
19    let prev = (res[part] = new ListNode(iter.val))
20    iter = iter.next
21    partSize--
22
23    // add the rest
24    while (partSize-- && iter) {
25      prev.next = new ListNode(iter.val)
26      prev = prev.next
27      iter = iter.next
28    }
29  }
30
31  return res
32}

References

Original problem

Similar problems

Rotate List

Odd Even Linked List