Best Solution || Beats 100% || All Languages || Easy Explained
\n\n# Intuition\nWe need to divide a linked list into k parts, such that the parts are as evenly distributed as possible. Each part should have roughly the same
![Screenshot 2024-09-08 133526.png](https://assets.leetcode.com/users/images/ce311849-4f22-492f-99da-af0d56e8fd7b_1725782780.8135855.png)\n\n# Intuition\nWe need to divide a linked list into k parts, such that the parts are as evenly distributed as possible. Each part should have roughly the same number of elements, and the earlier parts should contain more elements if there is a remainder. If there are fewer nodes than k, some parts will be null. This can be achieved by traversing the list to calculate its length and then determining how to distribute the nodes across k parts.\n\n# Approach\n1) Calculate the total length of the linked list by traversing it once.\n2) Determine the size of each part by dividing the total length by k. This will give the base size of each part. If there\u2019s a remainder, the first remainder parts will get one extra node.\n3) Split the list by traversing it again and breaking it into parts. For each part, assign the necessary number of nodes based on the calculated sizes.\n4) If the number of nodes is less than k, the extra parts will be null.\n\n# Complexity\n- Time complexity:\nThe time complexity is O(n), where n is the total number of nodes in the linked list. We traverse the list once to calculate its length and once more to split it into parts.\n\n- Space complexity:\nThe space complexity is O(k) for storing the k parts. No additional space is used other than the result array and the existing linked list, so the overall space complexity is O(k)\n![193730892e8675ebafc11519f6174bee5c4a5ab0.jpeg](https://assets.leetcode.com/users/images/8f688a71-6842-4327-8a9d-2eda980d94c3_1725782939.582792.jpeg)\n\n# Code\n```java []\n/**\n * Definition for singly-linked list.\n * public class ListNode {\n *     int val;\n *     ListNode next;\n *     ListNode() {}\n *     ListNode(int val) { this.val = val; }\n *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }\n * }\n */\nclass Solution {\n    public ListNode[] splitListToParts(ListNode head, int k) {\n        ListNode[] result = new ListNode[k];\n        \n        // Step 1: Calculate the total length of the linked list\n        int len = 0;\n        ListNode current = head;\n        while (current != null) {\n            len++;\n            current = current.next;\n        }\n        \n        // Step 2: Determine the base size and the remainder\n        int size = len / k;\n        int extra = len % k; // Number of parts that will have one extra element\n        \n        current = head;\n        for (int i = 0; i < k; i++) {\n            if (current == null) {\n                result[i] = null; // If the list is smaller than k, add null for empty parts\n            } else {\n                result[i] = current; // Start a new part\n                int partSize = size + (extra > 0 ? 1 : 0); // This part\'s size\n                extra--;\n                \n                // Move to the end of this part\n                for (int j = 1; j < partSize; j++) {\n                    if (current != null) {\n                        current = current.next;\n                    }\n                }\n                \n                // Break the current part from the rest of the list\n                if (current != null) {\n                    ListNode nextPart = current.next;\n                    current.next = null;\n                    current = nextPart;\n                }\n            }\n        }\n        \n        return result;\n    }\n}\n```\n```C++ []\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode() : val(0), next(nullptr) {}\n *     ListNode(int x) : val(x), next(nullptr) {}\n *     ListNode(int x, ListNode *next) : val(x), next(next) {}\n * };\n */\n\nclass Solution {\npublic:\n    vector<ListNode*> splitListToParts(ListNode* head, int k) {\n        vector<ListNode*> result(k, nullptr);\n        \n        // Step 1: Calculate the total length of the linked list\n        int len = 0;\n        ListNode* current = head;\n        while (current != nullptr) {\n            len++;\n            current = current->next;\n        }\n        \n        // Step 2: Determine the base size and the remainder\n        int size = len / k;\n        int extra = len % k; // Number of parts that will have one extra element\n        \n        current = head;\n        for (int i = 0; i < k; i++) {\n            if (current == nullptr) {\n                result[i] = nullptr; // If the list is smaller than k, add null for empty parts\n            } else {\n                result[i] = current; // Start a new part\n                int partSize = size + (extra > 0 ? 1 : 0); // This part\'s size\n                extra--;\n                \n                // Move to the end of this part\n                for (int j = 1; j < partSize; j++) {\n                    if (current != nullptr) {\n                        current = current->next;\n                    }\n                }\n                \n                // Break the current part from the rest of the list\n                if (current != nullptr) {\n                    ListNode* nextPart = current->next;\n                    current->next = nullptr;\n                    current = nextPart;\n                }\n            }\n        }\n        \n        return result;\n    }\n};\n```\n```Python []\n# Definition for singly-linked list.\n# class ListNode(object):\n#     def __init__(self, val=0, next=None):\n#         self.val = val\n#         self.next = next\nclass Solution(object):\n    def splitListToParts(self, head, k):\n        """\n        :type head: ListNode\n        :type k: int\n        :rtype: List[ListNode]\n        """\n        result = [None] * k  # Initialize the result list with None values\n        \n        # Step 1: Calculate the total length of the linked list\n        length = 0\n        current = head\n        while current:\n            length += 1\n            current = current.next\n        \n        # Step 2: Determine the base size and the remainder\n        size = length // k  # Base size of each part\n        extra = length % k  # Number of parts that will have one extra element\n        \n        current = head\n        for i in range(k):\n            if not current:\n                result[i] = None  # If the list is smaller than k, add None for empty parts\n            else:\n                result[i] = current  # Start a new part\n                part_size = size + (1 if extra > 0 else 0)  # Determine the size of this part\n                extra -= 1\n                \n                # Move to the end of this part\n                for j in range(1, part_size):\n                    if current:\n                        current = current.next\n                \n                # Break the current part from the rest of the list\n                if current:\n                    next_part = current.next\n                    current.next = None\n                    current = next_part\n        \n        return result\n\n```\n``` Javascript []\n/**\n * Definition for singly-linked list.\n * function ListNode(val, next) {\n *     this.val = (val===undefined ? 0 : val)\n *     this.next = (next===undefined ? null : next)\n * }\n/**\n * @param {ListNode} head\n * @param {number} k\n * @return {ListNode[]}\n */\nvar splitListToParts = function(head, k) {\n    let result = new Array(k).fill(null); // Initialize result array with nulls\n\n    // Step 1: Calculate the total length of the linked list\n    let length = 0;\n    let current = head;\n    while (current) {\n        length++;\n        current = current.next;\n    }\n\n    // Step 2: Determine the base size and the remainder\n    let size = Math.floor(length / k); // Base size of each part\n    let extra = length % k;            // Number of parts that will have one extra element\n\n    current = head;\n    for (let i = 0; i < k; i++) {\n        if (!current) {\n            result[i] = null; // If the list is smaller than k, add null for empty parts\n        } else {\n            result[i] = current; // Start a new part\n            let partSize = size + (extra > 0 ? 1 : 0); // This part\'s size\n            extra--;\n            \n            // Move to the end of this part\n            for (let j = 1; j < partSize; j++) {\n                if (current) {\n                    current = current.next;\n                }\n            }\n            \n            // Break the current part from the rest of the list\n            if (current) {\n                let nextPart = current.next;\n                current.next = null;\n                current = nextPart;\n            }\n        }\n    }\n\n    return result;\n};\n\n```
['Linked List', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']