Leetcode - 725. Split Linked List in Parts
Tags: leetcode
Published: 2023-10-31 15:53:14

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kthhf05jz4w55one7jeb.png)

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

```javascript
 //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.

```javascript
 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

```javascript

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 . 

```javascript
/**
 * 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;
};

```