LeetCode: Split Linked List in Parts Solution

Naming is hard

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

Comments

Loading comments...

Tags

leetcode

linked list

Next Post

LeetCode: Sort Colors

Sep 26, 2022

Count and overwrite

Previous Post

HoningJS

Search Posts