【Video】Simple and Easy Solution  - Python, JavaScript, Java, C++
IntuitionCalculate length of linked list and get length of each sub list.Solution VideoPlease subscribe to my channel from here. I have 256 videos as of Septemb
# Intuition
Calculate length of linked list and get length of each sub list.

---

# Solution Video

### Please subscribe to my channel from here. I have 256 videos as of September 6th, 2023.

https://youtu.be/ir-tDj1kM5g

### In the video, the steps of approach below are visualized using diagrams and drawings. I'm sure you understand the solution easily!

### ⭐️⭐️ Don't forget to subscribe to my channel! ⭐️⭐️

**■ Subscribe URL**
http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1

---

# Approach
This is based on Python. Other might be different a bit.

1. **Calculate the length of the linked list**
   - Initialize a variable `length` to 0 to keep track of the number of nodes in the linked list.
   - Initialize a pointer `current` to the head of the linked list.
   - Use a `while` loop to traverse the linked list while updating `current` and incrementing `length` for each node in the list.

2. **Determine the size of each part**
   - Calculate `part_size` by dividing `length` by `k`. This gives you the base size of each part.
   - Calculate `larger_parts` by taking the remainder of `length` divided by `k`. This represents the number of parts that will have one extra element.

3. **Split the linked list into parts**
   - Initialize an empty list `result` to store the resulting linked list parts.
   - Reset the `current` pointer to the head of the linked list.
   - Use a `for` loop to iterate `k` times, where `k` is the number of parts to split the list into.
   - Calculate `sublist_size` based on whether the current part (`i`) should have an extra element. If `i` is less than `larger_parts`, add 1 to `part_size`; otherwise, use `part_size`.
   - If `sublist_size` is 0 (which can happen if `k` is greater than the length of the linked list), append `None` to the `result` list to represent an empty part.
   - Otherwise, create a `sublist_head` pointer to the current node, which will be the head of the sublist.
   - Use a nested `for` loop to traverse the sublist until you reach the end of the sublist (which is `sublist_size - 1` nodes). Update the `current` pointer accordingly.
   - Store the next node (`next_node`) after the sublist in `next_node`.
   - Set the `next` pointer of the current node to `None` to separate the sublist from the original list.
   - Append the `sublist_head` to the `result` list, representing one of the parts of the split linked list.
   - Update the `current` pointer to `next_node` to prepare for the next iteration.

4. **Return the result**
   - Return the `result` list, which contains the linked list split into parts.

This algorithm takes a linked list, calculates its length, determines the size of each part based on the desired number of parts, and then splits the linked list into those parts while maintaining the original order of elements.

# Complexity
- Time complexity: O(n) or O(n + k)
Depends on size of n and k.

- Space complexity: O(k)

```python []
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
        # Step 1: Calculate the length of the linked list
        length = 0
        current = head
        while current:
            length += 1
            current = current.next
        
        # Step 2: Determine the size of each part
        part_size = length // k
        larger_parts = length % k
        
        # Initialize a list to store the results
        result = []
        
        # Step 3: Split the linked list into parts
        current = head
        for i in range(k):
            sublist_size = part_size + 1 if i < larger_parts else part_size
            if sublist_size == 0:
                result.append(None)
            else:
                sublist_head = current
                for _ in range(sublist_size - 1):
                    current = current.next
                next_node = current.next
                current.next = None
                result.append(sublist_head)
                current = next_node
        
        return result
```
```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) {
    // Step 1: Calculate the length of the linked list
    let length = 0;
    let current = head;
    while (current) {
        length += 1;
        current = current.next;
    }

    // Step 2: Determine the size of each part
    const partSize = Math.floor(length / k);
    const largerParts = length % k;

    // Initialize an array to store the results
    const result = [];

    // Step 3: Split the linked list into parts
    current = head;
    for (let i = 0; i < k; i++) {
        const sublistSize = i < largerParts ? partSize + 1 : partSize;
        if (sublistSize === 0) {
            result.push(null);
        } else {
            const sublistHead = current;
            for (let j = 0; j < sublistSize - 1; j++) {
                current = current.next;
            }
            const nextNode = current.next;
            current.next = null;
            result.push(sublistHead);
            current = nextNode;
        }
    }

    return result;    
};
```
```java []
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        // Step 1: Calculate the length of the linked list
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length += 1;
            current = current.next;
        }

        // Step 2: Determine the size of each part
        int partSize = length / k;
        int largerParts = length % k;

        // Initialize an array to store the results
        ListNode[] result = new ListNode[k];

        // Step 3: Split the linked list into parts
        current = head;
        for (int i = 0; i < k; i++) {
            int sublistSize = (i < largerParts) ? (partSize + 1) : partSize;
            if (sublistSize == 0) {
                result[i] = null;
            } else {
                ListNode sublistHead = current;
                for (int j = 0; j < sublistSize - 1; j++) {
                    current = current.next;
                }
                ListNode nextNode = current.next;
                current.next = null;
                result[i] = sublistHead;
                current = nextNode;
            }
        }

        return result;        
    }
}
```
```C++ []
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        // Step 1: Calculate the length of the linked list
        int length = 0;
        ListNode* current = head;
        while (current) {
            length += 1;
            current = current->next;
        }

        // Step 2: Determine the size of each part
        int partSize = length / k;
        int largerParts = length % k;

        // Initialize a vector to store the results
        vector<ListNode*> result(k);

        // Step 3: Split the linked list into parts
        current = head;
        for (int i = 0; i < k; i++) {
            int sublistSize = (i < largerParts) ? (partSize + 1) : partSize;
            if (sublistSize == 0) {
                result[i] = nullptr;
            } else {
                ListNode* sublistHead = current;
                for (int j = 0; j < sublistSize - 1; j++) {
                    current = current->next;
                }
                ListNode* nextNode = current->next;
                current->next = nullptr;
                result[i] = sublistHead;
                current = nextNode;
            }
        }

        return result;        
    }
};
```

---

Thank you for reading my post.
⭐️ Please upvote it and don't forget to subscribe to my channel!

⭐️ Subscribe URL
http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1

https://youtu.be/pCc4kR-TdYs

['Linked List', 'C++', 'Java', 'Python3', 'JavaScript']