DEV Community

Rakesh Reddy Peddamallu
Rakesh Reddy Peddamallu

Posted on

Leetcode - 725. Split Linked List in Parts

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.

Image description

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
Enter fullscreen mode Exit fullscreen mode

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

    };
Enter fullscreen mode Exit fullscreen mode

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;
    };

Enter fullscreen mode Exit fullscreen mode

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;
};

Enter fullscreen mode Exit fullscreen mode

Top comments (0)