[C++] Simple Solution Explained, ~90% Time, ~30% Space
So, we have to go through the whole array first to get its length and that is a given - unless you go for some more memory expensive alternative and store all i
So, we have to go through the whole array first to get its length and that is a given - unless you go for some more memory expensive alternative and store all its nodes somewhere else, but frankly I would rather pass on such an option.\n\nThe variables we need to proceed:\n* `res`, a vector of `ListNode`s we will initialise already with the right size and all `NULL`s, to avoid reallocations;\n* `len`, to store the list length;\n* `parts`, an array of `int`s to keep track of how many nodes go on each slot of `res` - you might skip that, but I found that having it was just more convenient and for little cost;\n* `curr`, a `ListNode` convenience pointer, initialised to `root`.\n\nThe next step will be to go through the whole list advancing `curr` and increasing `len` at the same time.\n\nWe then go and populate `parts` - each cell taking a base value of `div` given by `len / k` and optionally incremented by `1` as long as we have to distribute extra nodes as initially stored in the remainder `rem`.\n\nMoving on to the final loop, running `k` times and taking each cell in `res` to be populated with the current node `curr`, plus a few others as long as `parts[i]-- > 1`; after that, we set `root` to be now the next following value and if `curr` is not already `NULL`, we cut the sublist right after that, setting `curr->next = NULL`.\n\nFinally, we can return `res` :)\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    vector<ListNode*> splitListToParts(ListNode* root, int k) {\n        // support variables\n        vector<ListNode*> res(k, NULL);\n        int len = 0, parts[k];\n        ListNode *curr = root;\n        while (curr) {\n            len++;\n            curr = curr->next;\n        }\n        // setting parts to store the amount of nodes in each bit\n        for (int i = 0, rem = len % k, div = len / k; i < k; i++) parts[i] = div + (rem ? (rem--, 1) : 0);\n        for (int i = 0; i < k; i++) {\n            // filling each slot in res with the proper amount of nodes\n            curr = root;\n            res[i] = curr;\n            // adding extra nodes if parts[i] was > 1\n            while (parts[i]-- > 1) {\n                curr = curr ? curr->next : curr;\n            }\n            // preparing root for the next iteration\n            root = curr ? curr->next : curr;\n            // cutting the current tail, if not NULL already\n            if (curr) curr->next = NULL;\n        }\n        return res;\n    }\n};\n```\n\nArray-less alternative - tested for a while and basically performance stays the same, with little surprise, considering `k` won\'t ever exceed `50`:\n\n```cpp\nclass Solution {\npublic:\n    vector<ListNode*> splitListToParts(ListNode* root, int k) {\n        // support variables\n        vector<ListNode*> res(k, NULL);\n        int len = 0, div, rem, currPart;\n        ListNode *curr = root;\n        while (curr) {\n            len++;\n            curr = curr->next;\n        }\n        // storing informations about each partition\n        rem = len % k;\n        div = len / k;\n        for (int i = 0; i < k; i++) {\n            currPart = div + (rem ? (rem--, 1) : 0);\n            // filling each slot in res with the proper amount of nodes\n            curr = root;\n            res[i] = curr;\n            // adding extra nodes if currPart was > 1\n            while (currPart-- > 1) {\n                curr = curr ? curr->next : curr;\n            }\n            // preparing root for the next iteration\n            root = curr ? curr->next : curr;\n            // cutting the current tail, if not NULL already\n            if (curr) curr->next = NULL;\n        }\n        return res;\n    }\n};\n```
['Linked List', 'C', 'C++']