We have to traverse the linked list to find the length of the list. Then we can calculate the size of each part and the number of extra nodes. We can split the linked list into parts by traversing the list again.
total size = 3, k = 5
[1, 1, 1, 0, 0]
0 0 0 0 0 // size = 3 / 5 = 0
1 1 1 0 0 // remain = 3 % 5 = 3 = [1 1 1 0 0]
total size = 10, k = 4
[3, 3, 2, 2]
2 2 2 2 // size = 10 / 4 = 2
1 1 0 0 // remain = 10 % 4 = 2 = [1 1 0 0 0]fun splitListToParts(head: ListNode?, k: Int): Array<ListNode?> {
val parts = Array<ListNode?>(k) { null }
val totalSize = getSize(head)
val size = totalSize / k
var remain = totalSize % k
var current: ListNode? = head
var previous: ListNode? = null
var kk = 0
// total size = 10, k = 4
// size = 2, remain = 2 - 1 - 1
// 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
// p c
// j = 1..2
// [0 -> 1 -> 2] [3 -> 4 -> 5] [6 -> 7] []
// kk
while (current != null) {
parts[kk++] = current
// Traverse with the size steps + 1 if there are remaining nodes
for (steps in 1..(size + (if (remain > 0) 1 else 0))) {
previous = current
current = current?.next
}
remain--
// Disconnect the previous node
previous?.next = null
}
return parts
}
private fun getSize(head: ListNode?): Int {
var size = 0
var current: ListNode? = head
while (current != null) {
current = current.next
size++
}
return size
}