Lets get into the solution of the problem .
Basically we need to split the linked list in k parts ,
lets say length is the length of linked list.
so base_size = Math.floor(length/k) ie each part will contain this many nodes. and there can be few nodes left those we call as extra items.
If you see this example , we need to split into 3 parts , and length of linked list is 10 , so the base size = Math.floor(10/3) = 3 , so there will be 1 node left ie extra = 1 . This extra item we distribute from start to end until it gets over , just like sweets š .
So the code goes like
//k is number of parts
let length = 0;
let parts = [];
//calculating length of linked list
let current = head ;
while(current){
current = current.next;
length++
}
let base_size = Math.floor(length/k); // these many items in each of bucket
let extra = length % k; // extra items
so parts here is an array which will store the linked lists after we split.
as u need to split into k parts , u will run a for loop k times.
for(let i = 0 ;i < k ;i++){
//rest of logic
};
Now we need to write a logic to split the linked lists , all we are going to do is to break the existing links and point them to new ones
for(let i = 0 ;i < k ;i++){
//rest of logic
let part_size = base_size + (extra > 0 ? 1 : 0);
let part_head = null, part_tail = null;
};
so basically we creating each part and then pushing into parts array ,
so we declared part_head and part_tail , two pointers for the head and tail of part both set to null initially
Now try to understand the below logic on paper then you will be able to understand .
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode[]}
*/
var splitListToParts = function(head, k) {
//k is number of parts
let current = head ;
let length = 0;
let parts = [];
while(current){
current = current.next;
length++
}
let base_size = Math.floor(length/k); // these many items in each of bucket
let extra = length % k; // extra items
current = head;
for(let i = 0 ;i < k ;i++){
let part_size = base_size + (extra > 0 ? 1 : 0);
let part_head = null, part_tail = null;
for (let j = 0; j < part_size; j++) {
if (!part_head) {
part_head = part_tail = current;
}else{
part_tail.next = current;
part_tail = part_tail.next;
}
if (current) {
current = current.next;
}
};
if (part_tail) {
part_tail.next = null;
}
parts.push(part_head);
extra = Math.max(extra - 1, 0);
};
return parts;
};
Top comments (0)